Paper deep dive
Overcoming Prior Barriers: Supervised Fine-Tuning under Long-Tail Distribution
Haohui Wang, Jiahao Xu, Wangzhi Zhan, Tong Zeng, Dongqi Fu, Hong Li, Swastik Roy, Naren Ramakrishnan, Chris North, Jian Kang, Yujun Yan, Dawei Zhou
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/11/2026, 2:08:13 AM
Summary
This paper introduces the concept of 'prior barrier' to quantify the pretrained support disparity between target and competing concepts in Supervised Fine-Tuning (SFT). It demonstrates that prior barriers follow a long-tail distribution, where tail concepts require significantly more instructions to overcome higher barriers. The authors derive a predictive risk bound linking prior barriers and accumulated evidence. Based on this, they propose PASS, an adaptive instruction selection method that estimates distinguishing evidence and allocates a limited SFT budget to under-represented concepts, outperforming state-of-the-art methods.
Entities (6)
Relation Signals (5)
Prior Barrier → follows → Long-Tail Distribution
confidence 95% · We observe that prior barriers follow a long-tail distribution, placing head and tail concepts at different starting points for SFT
PASS → outperforms → State-of-the-Art Methods
confidence 94% · Experiments show that our method consistently outperforms seven state-of-the-art instruction selection methods
PASS → addresses → Prior Barrier
confidence 92% · Motivated by this prior barrier-dependent demand, we propose PASS... adaptively allocates the selection budget toward concepts that remain insufficiently covered
Prior Barrier → determines → Instruction Demand
confidence 90% · A larger prior barrier indicates that more instructions is needed to achieve comparable performance.
Distinguishing Evidence → overcomes → Prior Barrier
confidence 88% · The amount of useful information depends on the instruction distribution... SFT instructions to contain information that distinguishes the target concept from its competing concepts.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Supervised fine-tuning (SFT) adapts pretrained large language models (LLMs) to downstream tasks, but the required concepts can receive substantially different levels of pretrained support. Frequent concepts are more likely to be well learned, whereas rare concepts may remain weakly represented. We introduce a novel notion named prior barrier to quantify how strongly the pretrained model supports competing concepts over the target concept. We observe that prior barriers follow a long-tail distribution, placing head and tail concepts at different starting points for SFT: head concepts face lower prior barriers, whereas tail concepts require additional instructions to overcome their higher prior barriers. Our theoretical analysis further derives a predictive risk bound for SFT under long-tail prior barriers, explicitly characterizing how the prior barrier and accumulated SFT evidence jointly determine predictive performance. Motivated by this prior barrier-dependent demand, we propose PASS, an adaptive SFT instruction selection method that constructs reference-derived concepts and estimates the distinguishing evidence provided by each instruction, and adaptively allocates the selection budget toward concepts that remain insufficiently covered under the current selection. In this way, PASS jointly considers which instructions can provide useful evidence and where additional supervision is needed under a limited budget. Experiments show that our method consistently outperforms seven state-of-the-art instruction selection methods on four backbone-budget settings. An ablation study further shows that PASS's adaptive allocation consistently improves over uniform allocation.
Tags
Links
- Source: https://arxiv.org/abs/2610.12345v1
- Canonical: https://arxiv.org/abs/2610.12345v1
Trouble viewing inline? Open PDF directly →
Full Text
63,379 characters extracted from source content.
Expand or collapse full text
Overcoming Prior Barriers: Supervised Fine-Tuning under Long-Tail Distribution Haohui Wang, Jiahao Xu, Wangzhi Zhan, Tong Zeng Dongqi Fu, Hong Li, Swastik Roy, Naren Ramakrishnan Chris North, Jian Kang, Yujun Yan, Dawei Zhou Virginia Tech Amazon Meta MBZUAI Dartmouth College Abstract Supervised fine-tuning (SFT) adapts pretrained large language models (LLMs) to downstream tasks, but the required concepts can receive substantially different levels of pretrained support. Frequent concepts are more likely to be well learned, whereas rare concepts may remain weakly represented. We introduce a novel notion named prior barrier to quantify how strongly the pretrained model supports competing concepts over the target concept. We observe that prior barriers follow a long-tail distribution, placing head and tail concepts at different starting points for SFT: head concepts face lower prior barriers, whereas tail concepts require additional instructions to overcome their higher prior barriers. Our theoretical analysis further derives a predictive risk bound for SFT under long-tail prior barriers, explicitly characterizing how the prior barrier and accumulated SFT evidence jointly determine predictive performance. Motivated by this prior barrier-dependent demand, we propose PASS, an adaptive SFT instruction selection method that constructs reference-derived concepts and estimates the distinguishing evidence provided by each instruction, and adaptively allocates the selection budget toward concepts that remain insufficiently covered under the current selection. In this way, PASS jointly considers which instructions can provide useful evidence and where additional supervision is needed under a limited budget. Experiments show that our method consistently outperforms seven state-of-the-art instruction selection methods on four backbone-budget settings. An ablation study further shows that PASS’s adaptive allocation consistently improves over uniform allocation. 1 Introduction Supervised fine-tuning (SFT) is widely used to adapt pretrained large language models (LLMs) to downstream requirements such as mathematical reasoning, instruction following, factuality, and domain-specific behaviors (Ouyang et al., 2022; Zhou et al., 2023; Yue et al., 2023). In practice, the available instruction pool can be much larger than the amount of data that can be used for fine-tuning, while candidate instructions can also vary substantially in quality, making data selection an important part of post-training (Xia et al., 2024). Given a downstream task and a large pool of candidate instructions, which examples should be selected under a limited SFT budget? Recent studies show that carefully selected subsets can match or outperform substantially larger SFT datasets (Zhou et al., 2023; Chen et al., 2024; Xia et al., 2024; Liu et al., 2024b), underscoring the importance of selecting valuable instructions under a limited SFT budget. A central difficulty for effective SFT instruction selection is that the concepts required by the downstream task can receive substantially different levels of support from the pretrained model. Each task can involve a collection of concepts, ranging from common reasoning patterns and broadly observed instructions to rare knowledge and specialized behaviors. Frequently occurring concepts receive broader exposure during pretraining and are therefore more likely to receive strong support from the pretrained model, whereas rare concepts may remain weakly supported (Kandpal et al., 2023; Razeghi et al., 2022; Gekhman et al., 2024). We introduce a novel notion named prior barrier to quantify how strongly the pretrained model supports competing concepts over the target concept. Different prior barriers place target concepts at different starting points for SFT: a larger prior barrier indicates that more instructions is needed to achieve comparable performance. As illustrated in Figure 1, we observe a long-tail distribution in prior barriers, where head concepts face low prior barriers while tail concepts face high barriers, thus requiring more instructions. Under a limited SFT budget, effective selection should determine how to allocate instructions across concepts and which candidate instructions provide useful evidence for each concept (Chen et al., 2023; Dai et al., 2026). Figure 1: Illustration of the long-tail distribution of prior barriers using the Navier–Stokes existence and smoothness problem as an example. These observations motivate two fundamental challenges: C1. Theoretical foundation. How does the SFT evidence overcome the prior barrier, and how does this determine the amount of instructions required to learn a target concept? C2. Computational framework. How can we develop a method that identifies which instructions in the candidate pool provide useful evidence for each concept while adaptively allocating a limited selection budget according to concept-level demand? To address C1, we first characterize the role of the prior barrier in SFT. In the head case, the target concept already receives sufficient pretrained support. SFT can move toward the target with relatively limited evidence. In the tail case, the target concept faces a positive prior barrier, so the accumulated evidence must additionally overcome this disadvantage from pretraining. This interaction yields different instruction demands across concepts. We further derive a predictive risk bound that connects the demands to model performance by quantifying predictive risk in terms of the prior barrier and the distinguishing evidence provided by the selected instructions. To address C2, we propose Prior-barrier Aware SFT Instruction Selection (PASS), an adaptive SFT instruction selection framework motivated by the prior barrier-dependent demand. It first constructs a reference-derived concept space and estimates concept-specific distinguishing evidence for each candidate instruction. PASS further estimates the prior barrier and existing pretrained support of each concept to characterize how strongly that concept calls for additional SFT instruction. It then adaptively allocates the selection budget toward concepts that remain under-represented. As a result, PASS jointly determines which candidate instructions provide useful evidence and where the limited SFT budget should be allocated. Our empirical results show that PASS outperforms seven state-of-the-art instruction selection methods in all four backbone-budget settings. Ablation results further demonstrate the benefit of adaptively allocating the SFT budget according to prior barrier. The source code will be released upon publication. 2 Preliminary In this section, we introduce the background, including a Bayesian concept-space view of SFT, and give the formal problem definition. Notations. We consider a concept space Θ , where each concept θ∈Θθ∈ describes a possible input–response relation through a conditional distribution Pθ(y∣x)P_θ(y x). Here, x denotes an instruction input or query and y denotes the corresponding response. For example, for a mathematical reasoning concept, x may be a mathematical problem and y its correct solution. We denote the target concept required by the downstream task as θ⋆θ . Pretraining does not provide equal support for all concepts. We represent this pretrained support by a distribution π(θ)π(θ) over Θ , where a larger π(θ)π(θ) indicates stronger pretrained support for concept θ. We interpret π as a prior distribution over concepts induced by pretraining. As a result, different target concepts can begin SFT from substantially different pretrained states. Supervised fine-tuning. SFT adapts a pretrained language model to the downstream task using a set of supervised instruction input–response pairs. Given an SFT dataset n=(xi,yi)i=1nD_n=\(x_i,y_i)\_i=1^n, where xix_i is the i-th instruction input and yiy_i is its target response, SFT updates the pretrained model to increase the likelihood of the target responses conditioned on their inputs. For an autoregressive language model, this conditional probability factorizes as Pθ(yi∣xi)=∏t=1TiPθ(yi,t∣xi,yi,<t)P_θ(y_i x_i)= _t=1^T_iP_θ(y_i,t x_i,y_i,<t), where TiT_i is the number of tokens in response yiy_i, yi,ty_i,t is the t-th token of yiy_i and yi,<ty_i,<t denotes its preceding response tokens. Standard SFT therefore trains the model by minimizing the token-level negative log-likelihood over the SFT dataset. We summarize the evidence provided by the SFT dataset for concept θ through its log-likelihood Sn(θ)=∑i=1nlogPθ(yi∣xi)S_n(θ)= _i=1^n P_θ(y_i x_i). We adopt a Bayesian concept-space view of SFT, where the pretrained distribution π serves as the prior and the supervised data update this prior through their likelihood. Let q denote a candidate distribution over the concept space Θ after observing the SFT dataset nD_n. We define (q)=−θ∼q[Sn(θ)]+DKL(q∥π)J(q)=-E_θ q [S_n(θ) ]+D_KL(q\|π), The posterior distribution is defined as qn⋆=argminq(q)q_n = _qJ(q), which takes the Gibbs-posterior form qn⋆(θ)=eSn(θ)π(θ)∫ΘeSn(u)π(u)λ(u)q_n (θ)= e^S_n(θ)π(θ) _ e^S_n(u)π(u)\,λ(du). Here, qn⋆(θ)q_n (θ) represents the updated support for concept θ, obtained by updating the pretrained prior π(θ)π(θ) with the likelihood evidence from the SFT data through Sn(θ)S_n(θ). Problem definition. Given a candidate SFT pool =(xi,yi)i=1ND=\(x_i,y_i)\_i=1^N, a selection budget n, and a reference set T representing the desired behaviors in the downstream task with a long-tail distribution of prior barriers across concepts, our goal is to find a subset of instructions n⊆D_n with |n|=n|D_n|=n such that fine-tuning the pretrained model on nD_n achieves strong overall performance on the downstream task. 3 Theoretical Analysis In this section, we develop a theoretical analysis of how pretrained support and SFT evidence jointly shape predictive performance. First, we study posterior concentration around the target concept, showing how the prior barrier and distinguishing evidence together determine whether SFT can move the concept distribution toward the target. Second, we derive a predictive risk bound that connects posterior concentration to predictive performance and shows how the head–tail gap translates into different generalization guarantees. Prior barrier. A pretrained model does not enter SFT from a neutral state: different concepts can receive substantially different levels of support from pretraining. This asymmetry is important because SFT adapts a pretrained model, where the target concept may compete with alternatives that are more strongly supported before fine-tuning begins. A key challenge is therefore to characterize this pretrained support relative to the target concept θ⋆θ and its competing concepts θ∈Θ∖θ⋆θ∈ \θ \. To this end, we consider concepts outside an r-neighborhood of the target concept Ar=θ∈Θ:‖θ−θ⋆‖≥rA_r= \θ∈ :\|θ-θ \|≥ r \. If θ⋆θ already receives stronger support than all concepts in ArA_r, the target concept does not face a pretrained disadvantage. Otherwise, some competing concept receives stronger pretrained support than θ⋆θ , placing the target at an initial disadvantage before SFT begins. We characterize this relative pretrained disadvantage through the prior barrier. Definition 1 (Prior barrier). The prior barrier at resolution r is B(r)=supθ∈Arlogπ(θ)π(θ⋆)B(r)= _θ∈ A_r π(θ)π(θ ). The prior barrier B(r)B(r) compares the pretrained support of the target concept with its strongest competing concept. We observe that prior barriers exhibit a long-tail distribution across concepts, with many concepts facing relatively small barriers and few concepts facing substantially larger ones. For the analysis below, we refer to B(r)≤0B(r)≤ 0 as the head case, where the target concept is at least as well supported as all concepts in ArA_r, and B(r)>0B(r)>0 as the tail case, where at least one competing concept receives stronger pretrained support than the target concept. Overcoming a positive prior barrier requires the SFT instructions to contain information that distinguishes the target concept from its competing concepts. The amount of useful information depends on the instruction distribution PXP_X: some instructions can clearly expose the difference between the target concept and an alternative concept, whereas others provide little distinguishing evidence. For a competing concept θ, define the expected evidence under PXP_X as K(θ)=x∼PX[KL(Pθ⋆(⋅∣x)∥Pθ(⋅∣x))]=x∼PXy∼Pθ⋆(⋅∣x)[logPθ⋆(y∣x)−logPθ(y∣x)].K(θ)=E_x P_X [KL (P_θ (· x)\|P_θ(· x) ) ]=E_ subarraycx P_X\\ y P_θ (· x) subarray [ P_θ (y x)- P_θ(y x) ]. (1) Thus, a larger K(θ)K(θ) means that the observed instruction input–response pair drawn from the instruction distribution provides stronger expected evidence for separating the target concept from θ. Because SFT requires distinguishing the target from all concepts outside its neighborhood, we focus on the hardest competitor. Definition 2 (Distinguishing Evidence). The distinguishing evidence for the target concept at resolution r is ϵ(r)=infθ∈ArK(θ)ε(r)= _θ∈ A_rK(θ). The target concept θ⋆θ is identifiable under the SFT instruction distribution PXP_X when ϵ(r)>0ε(r)>0. Learning the target concept requires the posterior distribution after SFT to place little mass on the competing concepts in ArA_r, that is, to make qn⋆(Ar)q_n (A_r) small. The two central quantities governing it are B(r)B(r), which measures how much pretrained disadvantage must be overcome, and nϵ(r)nε(r), which measures how much distinguishing evidence SFT accumulates. As the number of SFT instructions increases, the accumulated evidence grows with nϵ(r)nε(r). Therefore, once this evidence is sufficient to overcome the pretrained disadvantage, the posterior can concentrate around the target concept. Theorem 1 (Posterior Concentration). Fix r>0r>0 such that Ar≠∅A_r≠ and ϵ(r)>0ε(r)>0, and let m(r)>0m(r)>0 denote the normalized prior mass in a sufficiently small neighborhood of the target concept θ⋆θ . Under the assumptions given in Appendix A.1, for any η∈(0,1)η∈(0,1), if n≥nsep(r,η)n≥ n_sep(r,η) where nsep(r,η)n_sep(r,η) denotes the sample-size threshold, with probability at least 1−η1-η over the SFT dataset nD_n, qn⋆(Ar)≤min1,1m(r)exp(B(r)−nϵ(r)8).q_n (A_r)≤ \1, 1m(r) (B(r)- nε(r)8 ) \. (2) Proof. The proof is provided in Appendix A.2. ∎ Theorem 1 shows that, once the target concept is identifiable under the SFT distribution, sufficiently many SFT examples drive posterior mass away from competing concepts and toward the target concept. Since the prior barrier is fixed while the accumulated distinguishing evidence grows with n, the concentration error decreases exponentially as supervision increases. The amount of supervision required, however, differs between the head and tail cases. Corollary 1 (Head–Tail Supervision Gap). Under the conditions of Theorem 1, let δ∈(0,1)δ∈(0,1) be a desired posterior error. The head case B(r)≤0B(r)≤ 0 satisfies qn⋆(Ar)≤δq_n (A_r)≤δ whenever n≥max8ϵ(r)(log1m(r)δ)+,nsep(r,η),n≥ \ 8ε(r) ( 1m(r)δ )_+,n_sep(r,η) \, (3) where (a)+=maxa,0(a)_+= \a,0\. The tail case B(r)>0B(r)>0 satisfies qn⋆(Ar)≤δq_n (A_r)≤δ whenever n≥max8ϵ(r)(B(r)+log1m(r)δ)+,nsep(r,η).n≥ \ 8ε(r) (B(r)+ 1m(r)δ )_+,n_sep(r,η) \. (4) Proof. The proof is provided in Appendix A.3. ∎ The posterior concentration result explains when SFT places most of its concept-level support near the target concept. We now ask whether this concept-level concentration also leads to predictive performance. Define the posterior predictive distribution as Pqn⋆(y∣x)=∫ΘPθ(y∣x)qn⋆(θ)P_q_n (y x)= _ P_θ(y x)q_n (dθ), and measure its excess predictive log-loss relative to the target concept by ℰn=x∼PX[DKL(Pθ⋆(⋅∣x)∥Pqn⋆(⋅∣x))]E_n=E_x P_X [D_KL (P_θ (· x)\|P_q_n (· x) ) ]. We now establish how posterior concentration around the target concept translates into predictive performance for SFT. Theorem 2 (Predictive Risk Bound). Let α(r)=x∼PX[sup‖θ−θ⋆‖<rDKL(Pθ⋆(⋅∣x)∥Pθ(⋅∣x))]α(r)=E_x P_X [ _\|θ-θ \|<rD_KL (P_θ (· x)\|P_θ(· x) ) ] denote the worst local predictive discrepancy within distance r of the target concept, and let Mr<∞M_r<∞ be a uniform upper bound on the predictive KL discrepancy for competing concepts in ArA_r. Under the assumptions stated in Appendix A.1, SFT dataset nD_n satisfies ℰn≤α(r)+Mrqn⋆(Ar).E_n≤α(r)+M_rq_n (A_r). (5) Consequently, under the conditions of Theorem 1, with probability at least 1−η1-η, ℰn≤α(r)+Mrmin1m(r)exp(B(r)−nϵ(r)8),1.E_n≤α(r)+M_r \ 1m(r) (B(r)- nε(r)8 ),1 \. (6) Proof. The proof is provided in Appendix A.4. ∎ Theorem 2 shows that predictive risk depends on two terms: how well concepts near the target concept approximate its predictions, and how much posterior mass remains on competing concepts. As SFT concentrates the posterior around the target concept, the contribution from competing concepts decreases, leading to a tighter predictive risk bound. In particular, if SFT achieves qn⋆(Ar)≤δq_n (A_r)≤δ, then ℰn≤α(r)+MrδE_n≤α(r)+M_rδ. Thus, a target concept in the head case can reach a given predictive risk with less supervision, while a target concept in the tail case must first accumulate additional evidence to overcome its positive prior barrier. As a result, the tail case generally requires more SFT instructions to reach the same level of predictive risk. Figure 2: The proposed prior-barrier aware SFT instruction selection (PASS) framework. 4 Method Our theoretical analysis shows that achieving a small predictive risk requires SFT instructions to provide sufficient evidence for distinguishing the target concept from competing concepts. It further reveals different instruction requirements in the head and tail cases: a tail target concept requires additional instructions to overcome its positive prior barrier. These results motivate us to consider both how much distinguishing evidence each candidate instruction provides and how a fixed instruction budget should be allocated across target concepts with asymmetric pretrained support. In this section, we introduce PASS (shown in Figure 2), which consists of two major modules: M1. Distinguishing evidence estimation and M2. Prior barrier-aware instruction allocation. Accordingly, M1 constructs reference-derived concepts and estimates evidence for each candidate instruction by contrasting its support for the desired concept against relevant competing concepts. M2 uses the pretrained model to estimate the barrier and existing support of each concept, and incrementally allocates instructions according to both concept-level demand. 4.1 M1: Distinguishing Evidence Estimation Given a reference set T, we first construct a finite empirical discretization of the concept space Θ introduced in Section 2. We encode each reference instruction input x together with its target response y using the pretrained model M0M_0 to extract a response representation z(x,y)∈ℝdz(x,y) ^d. We hierarchically cluster these reference representations, recursively splitting clusters that do not satisfy a coherence criterion. We measure coherence by the concentration of cosine similarity between the representations in a cluster and their centroid, and stop splitting once each cluster is sufficiently coherent. The resulting clusters instantiate a finite set of target concepts Θ=θ1,…,θC = _1,…, _C, where C is the number of concepts. Each concept θ therefore corresponds to a subset θ⊆T_θ of reference instructions that exhibit a coherent representation. We represent the desired representation of concept θ by the normalized centroid of the representations in θT_θ: pθ=Norm(1|θ|∑(x,y)∈θz(x,y)),p_θ=Norm ( 1|T_θ| _(x,y) _θz(x,y) ), (7) where Norm(v)=v‖v‖2Norm(v)= v\|v\|_2. To construct competing representations, we keep the same instruction inputs in θT_θ but replace their target responses with corresponding wrong responses, using available incorrect alternatives together with incorrect responses produced by M0M_0. These wrong responses may reflect multiple competing concepts for the same concept. For concept θ, let θkW_θ k denote the set of wrong response instructions corresponding to its k-th competing concept, with k=1,…,Kθk=1,…,K_θ, where KθK_θ denotes the number of competing concepts associated with target concept θ. We represent each competing representation by the normalized centroid: nθk=Norm(1|θk|∑(x,y~)∈θkz(x,y~)),k=1,…,Kθ,n_θ k=Norm ( 1|W_θ k| _(x, y) _θ kz(x, y) ), k=1,…,K_θ, (8) where y~ y denotes a wrong response. The resulting set θ=nθ1,…,nθKθN_θ=\n_θ 1,…,n_θ K_θ\ defines the competing representations of concept θ. Our theoretical analysis suggests that a instruction may provide different distinguishing evidence for different concepts. We therefore evaluate candidate instruction (xi,yi)∈(x_i,y_i) separately against every concept. Let zi=z(xi,yi)z_i=z(x_i,y_i) be the representation of the i-th instruction. For concept θ, we measure its similarity to the desired representation and to the closest competing representation as sθ+(zi)=Sim(zi,pθ),sθ−(zi)=maxv∈θSim(zi,v),s_θ^+(z_i)=Sim(z_i,p_θ), s_θ^-(z_i)= _v _θSim(z_i,v), (9) where SimSim denotes cosine similarity. The difference sθ+(zi)−sθ−(zi)s_θ^+(z_i)-s_θ^-(z_i) indicates whether the candidate favors the desired representation of concept θ over its strongest competitor. For directly comparable across concepts, we calibrate this difference using statistics estimated from the reference responses of each concept. We define the empirical distinguishing evidence as ϵiθ=Calibθ(sθ+(zi),sθ−(zi)), _iθ=Calib_θ (s_θ^+(z_i),s_θ^-(z_i) ), (10) with Calibθ(s+,s−)=rθ(s+,s−)s+−s−σθCalib_θ(s^+,s^-)=r_θ(s^+,s^-) s^+-s^- _θ. Here, rθ(s+,s−)∈[0,1]r_θ(s^+,s^-)∈[0,1] is a relevance factor determined by the candidate’s affinity maxs+,s− \s^+,s^-\ relative to the affinity observed for the reference responses of concept θ. It downweights candidates that are far from both the desired and competing representations while preserving candidates that are strongly aligned with either side. The scale σθ>0 _θ>0 normalizes the similarity difference between sθ+s_θ^+ and sθ−s_θ^- for concept θ, making evidence magnitudes comparable across concepts. Directly estimating the theoretical distinguishing evidence requires conditional response distributions, which are generally unavailable in practice. We therefore use the calibrated similarity margin as an empirical surrogate. A positive ϵiθ _iθ indicates that candidate i provides evidence in favor of the desired representation of concept θ, whereas a negative value indicates stronger support for a competing concept. M1 outputs the evidence matrix [ϵiθ]∈ℝN×C[ _iθ] ^N× C for the reference-derived concepts rather than collapsing each candidate into a single score. 4.2 M2: Prior Barrier-Aware Instruction Allocation M1 identifies how much distinguishing evidence each candidate can provide for different concepts, while the remaining question is how to allocate a fixed selection budget across concepts with different demands. Our theoretical analysis shows that a tail concept requires additional instructions to overcome its pretrained disadvantage. M2 therefore estimates concept-level demand from the prior barrier and incrementally allocates instructions as useful evidence is accumulated. Since the theoretical prior barrier is not directly observable, we estimate it empirically from the pretrained model’s responses. We let the pretrained model M0M_0 generate a response y^∼M0(⋅∣x) y M_0(· x) and obtain its representation z^=z(x,y^) z=z(x, y) for each instruction input in θT_θ. The prior barrier of concept θ is estimated from the normalized difference between competing and desired representations, Bθ=Agg(x,y)∈θ[sθ−(z^)−sθ+(z^)σθ],B_θ=Agg_(x,y) _θ [ s_θ^-( z)-s_θ^+( z) _θ ], (11) where AggAgg denotes the aggregation over the reference instructions of concept θ. Complementary to this relative barrier, we separately estimate the absolute pretrained support for the target concept by measuring whether the generated response y y lies sufficiently close to the desired representation pθp_θ: γθ=1|θ|∑(x,y)∈θSupportθ(Sim(z^,pθ)), _θ= 1|T_θ| _(x,y) _θSupport_θ (Sim( z,p_θ) ), (12) where Supportθ(⋅)∈[0,1]Support_θ(·)∈[0,1] calibrates the similarity to pθp_θ using the similarities observed from the target responses of concept θ. A larger γθ _θ indicates stronger pretrained support for the target concept. A concept should receive more instruction when the pretrained model exhibits a higher prior barrier and weaker absolute target support. We therefore define its allocation weight as Aθ=exp(Bθ)/γθ∑θ′∈Θexp(Bθ′)/γθ′,A_θ= (B_θ)/ _θ _θ ∈ (B_θ )/ _θ , (13) so that ∑θ∈ΘAθ=1 _θ∈ A_θ=1. While AθA_θ characterizes the relative instruction demand of each concept, the final selected subset should also account for how selected instructions contribute positive and negative distinguishing evidence, as well as the redundancy among their representations. We therefore define the selection objective by jointly modeling these three factors: F()=∑θ∈ΘAθRθ+()−λh∑θ∈ΘAθRθ−()−λrD(),F(S)= _θ∈ A_θR_θ^+(S)- _h _θ∈ A_θR_θ^-(S)- _rD(S), (14) where Rθ+R_θ^+ rewards positive distinguishing evidence for concept θ, Rθ−R_θ^- penalizes negative distinguishing evidence for concept θ, D penalizes redundant selections, and λh _h and λr _r denote the weights of harm penalty and redundancy penalty. For positive evidence, repeatedly selecting instructions for the same concept should yield diminishing returns. We therefore define Rθ+()=1−exp−βθ+∑i∈ϵiθ+R_θ^+(S)=1- \-β^+_θ _i _iθ^+ \, where ϵiθ+=(ϵiθ)+ _iθ^+=( _iθ)_+. The coefficient βθ+>0β^+_θ>0 controls how quickly the positive reward for concept θ saturates. Concepts with richer available evidence therefore saturate more slowly, while the marginal reward decreases as more positive evidence has already been selected. For negative evidence, we define Rθ−()=∑i∈[expβ−ϵiθ−1]R_θ^-(S)= _i [ \β^- _iθ^- \-1 ], where ϵiθ−=(−ϵiθ)+ _iθ^-=(- _iθ)_+, and β−>0β^->0 is an evidence scale shared across concepts for negative contributions. This term assigns a larger penalty to instructions that more strongly favor competing concepts. Finally, we discourage selecting instructions that provide highly redundant information. We define D()=2||(||−1)∑i,j∈Sim(zi,zj),D(S)= 2|S|(|S|-1) _ subarrayci,j subarraySim(z_i,z_j),. This term encourages the selected subset to cover distinct regions of the response representation space. We initialize =∅S= and greedily select the instruction with the largest marginal gain, i⋆∈argmaxi:(xi,yi)∈∖[F(∪(xi,yi))−F()].i ∈ _i:(x_i,y_i) [F (S∪\(x_i,y_i)\ )-F(S) ]. (15) After each selection, the selection objective is updated. The procedure stops when ||=n|S|=n, yielding the subset used for SFT. Algorithm 1 in Appendix B summarizes the complete procedure. 5 Experiments In this section, we evaluate the performance of our method on four backbone-budget settings. PASS exhibits superior performance compared to various state-of-the-art baselines (Section 5.2). Further, through the ablation study (Section 5.3), we demonstrate the necessity of each component of PASS. We also report parameter analysis (Section 5.4), complexity sensitivity (Appendix C.2), and the composition of instructions selected by different instruction selection methods (Appendix C.3). 5.1 Experiment Setup Candidate pool and target tasks. The candidate pool contains 300,932 instruction–response examples drawn from five open instruction datasets: FLAN V2 (Longpre et al., 2023), OASST1 (Köpf et al., 2023), WizardLM (Xu et al., 2024), Dolly (Conover et al., 2023) and Stanford Alpaca (Taori et al., 2023). To evaluate SFT instruction selection across concepts with long-tail prior barrier, we construct a downstream task spanning five capabilities: broad knowledge, multi-step reasoning, mathematics, truthfulness, and multilingual extractive QA. We form the reference set from examples covering these capabilities so that instruction selection is evaluated against the full range of target concepts. As shown in Figure 3, the prior barrier scores of the concepts in the reference set exhibit a long-tail distribution, providing a suitable setting for evaluating SFT under the long-tail distribution. Figure 3: Long-tail distribution of prior barrier over the reference-derived concepts. Backbones, budgets, and metrics. The main comparisons use Mistral-7B (Jiang et al., 2023) and Qwen2.5-7B (Qwen et al., 2024). We select n∈5,000,10,000n∈\5,000,10,000\ records, corresponding to approximately 1.66%1.66\% and 3.32%3.32\% of the original candidate pool. Within each backbone and budget, all selectors share the fine-tuning settings, the training recipe uses three epochs of LoRA (Hu et al., 2021). We report the overall performance on the downstream task (the macro-average of the five capability benchmark scores). Baselines. We compare against Base (backbone without fine-tuning) and seven instruction selection methods, including Random that samples uniformly; representation-based RDS+ (Ivison et al., 2025); gradient-based LESS (Xia et al., 2024); TSDS that uses optimal transport (Liu et al., 2024c); TADS that combines divisity selections by voting (Cheng et al., 2026); answer-divergence-based ADG (Li et al., 2026); and instance-quality filtering by DEITA (Liu et al., 2024b). Table 1: Overall downstream performance on Mistral-7B and Qwen2.5-7B at two selection budgets. The best and second-best results within each model and budget are shown in bold and underlined. Mistral-7B Qwen2.5-7B Method n=5,000n=5,000 n=10,000n=10,000 n=5,000n=5,000 n=10,000n=10,000 Base (no SFT) 26.9 26.9 52.8 52.8 Random 49.3 50.4 61.7 65.6 RDS+ 49.9 50.3 64.3 63.4 LESS 47.7 50.3 60.3 59.9 TSDS 49.4 49.8 63.1 63.0 TADS 48.7 50.9 64.6 63.2 ADG 50.0 50.9 62.4 64.1 DEITA 50.6 48.9 60.7 62.8 PASS 51.5 51.8 64.8 65.6 Table 2: Budget-aware instruction allocation versus uniform instruction allocation. Δuni=PASS−Uniform _uni= PASS- Uniform. Bold identifies the better results. n=5,000n=5,000 n=10,000n=10,000 Backbone PASS Uniform Δuni _uni PASS Uniform Δuni _uni Mistral-7B 51.46 51.14 +0.32+0.32 51.81 51.54 +0.26+0.26 Qwen2.5-7B 64.77 64.48 +0.29+0.29 65.60 65.03 +0.56+0.56 Table 3: Parameter sensitivity of PASS. Δdef _def is the difference relative to the default setting. Setting λh _h λr _r Mean Δdef _def Default 1.0 0.10 51.46 0.00 +0.00 Weak harm penalty 0.5 0.10 51.56 +0.10+0.10 Strong harm penalty 2.0 0.10 50.54 −0.92-0.92 Weak redundancy penalty 1.0 0.05 50.96 −0.50-0.50 Strong redundancy penalty 1.0 0.20 52.21 +0.75+0.75 5.2 Performance Analysis Table 3 shows that PASS consistently achieves the best overall performance across all four settings, indicating consistent gains across backbone choice and selection budget. In particular, on Mistral-7B, PASS reaches a score of 51.551.5 with 5,0005,000 selected instructions, higher than every competing selector using twice the budget (n=10,000n=10,000), where the strongest overall performance is 50.950.9. This result indicates that a better composition of the selected subset can compensate for a substantially smaller SFT budget. In contrast, other selection methods may identify individually relevant or high-quality instructions, but they fail to adaptively cover all capabilities required for downstream tasks, resulting in poor overall performance. This is particularly evident on Qwen2.5-7B with n=10,000n=10,000, where Random achieves an average score of 65.665.6, outperforming all other baselines. Taken together, these results support the motivation behind PASS: the key challenge is not only to identify useful individual instructions, but also to adaptively allocate budget based on the prior barrier. 5.3 Ablation Study We compare our budget-aware instruction allocation strategy with uniform instruction allocation. Under uniform variant, we allocate an equal budget of n/5n/5 separately to each of the five capabilities in the downstream task. Table 3 shows that budget-aware allocation consistently outperforms uniform allocation across both backbones and both selection budgets. On Mistral-7B, PASS improves the average score by 0.320.32 and 0.260.26 points at n=5,000n=5,000 and n=10,000n=10,000, respectively. A similar trend is observed on Qwen2.5-7B, where the gains are 0.290.29 and 0.560.56 points. These results indicate that an equal per-capability assignment is suboptimal. In contrast, PASS adaptively allocates instructions according to the prior barrier, thereby making better use of the limited SFT budget. 5.4 Parameter Analysis We study two hyperparameters of our method: (1) the harm coefficient λh _h weights the penalty on negative distinguishing evidence, and (2) the redundancy coefficient λr _r controls the penalty on redundant selections. Table 3 reports the overall performance under varying λh _h and λr _r using Mistral-7B with n=5,000n=5,000 selected instructions. The fluctuation of the performance is less than 2%2\%, showing PASS is reliable and not sensitive to the hyperparameters over a wide range. 6 Related Work Instruction selection for supervised fine-tuning (SFT) has been studied from several perspectives, including instance quality, model-dependent utility, target-aware matching. Early work shows that small but carefully selected instruction sets can be highly effective (Zhou et al., 2023; Chen et al., 2024). Methods such as DEITA further combine response quality, instruction complexity, and embedding diversity to identify informative and non-redundant examples (Liu et al., 2024b). Other approaches make selection dependent on the model itself. For example, ADG measures the divergence among multiple generated answers to estimate instruction utility (Li et al., 2026), while related methods use model difficulty, uncertainty, or response likelihood as selection signals (Li et al., 2024; Liu et al., 2024a; Zhang et al., 2025). Recent work uses downstream references to identify instructions that are relevant to the target task. LESS estimates candidate influence through low-rank gradient similarity to reference examples (Xia et al., 2024); RDS+ retrieves candidates using pretrained representations (Ivison et al., 2025); TSDS aligns the selected subset with the target distribution through optimal transport (Liu et al., 2024c); and TADS uses LLM-inferred proxy labels to improve task-aware distribution matching (Cheng et al., 2026). These methods provide strong mechanisms for estimating whether an instruction is relevant to downstream requirements, but generally summarize candidate utility through similarity, influence, or distribution matching. Beyond candidate scoring, several methods consider how supervision should be distributed across skills or tasks. Skill-It adapts training mixtures according to skill dependencies (Chen et al., 2023), while MIG and BIDS dynamically prioritize informative or underrepresented targets (Chen et al., 2025; Dai et al., 2026). Our work complements these approaches by connecting instruction allocation to unequal pretrained support through prior barrier. It combines prior barrier with distinguishing evidence to adaptively allocate the SFT budget. 7 Conclusion This work studies supervised fine-tuning under long-tail distributions, where different target concepts can receive substantially different levels of pretrained support. We introduce the prior barrier to characterize this difference, and observe that prior barriers exhibit a long-tail distribution. Our theoretical analysis shows that the prior barrier and instruction evidence jointly determine the number of instructions required during SFT: head concepts require relatively limited additional supervision, whereas tail concepts require more evidence to overcome their prior barriers. Guided by this analysis, we propose PASS, which estimates concept-specific distinguishing evidence and adaptively allocates a limited SFT budget according to the prior barrier. PASS achieves the best overall performance compared with seven instruction selection baselines in all four backbone-budget settings, while its adaptive allocation consistently improves over uniform allocation. These results show that effective SFT instruction selection should account for both the evidence provided by candidate instructions and the adaptive allocation based on the prior barrier. References Chen et al. (2024) L. Chen, S. Li, J. Yan, H. Wang, K. Gunaratna, V. Yadav, Z. Tang, V. Srinivasan, T. Zhou, H. Huang, and H. Jin AlpaGasus: training a better alpaca with fewer data. External Links: 2307.08701, Link Cited by: §1, §6. Chen et al. (2023) M. F. Chen, N. Roberts, K. Bhatia, J. Wang, C. Zhang, F. Sala, and C. Ré Skill-it! a data-driven skills framework for understanding and training language models. External Links: 2307.14430, Link Cited by: §1, §6. Chen et al. (2025) Y. Chen, Y. Li, K. Hu, Z. Ma, H. Ye, and K. Chen MIG: automatic data selection for instruction tuning by maximizing information gain in semantic space. In Findings of the Association for Computational Linguistics: ACL 2025, p. 9902–9915. External Links: Document, Link Cited by: §6. Cheng et al. (2026) H. Cheng, R. Zhang, L. Li, N. Di, J. Wei, Z. Zhu, and B. Han Task-aware data selection via proxy-label enhanced distribution matching for LLM finetuning. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §5.1, §6. Clark et al. (2020) J. H. Clark, E. Choi, M. Collins, D. Garrette, T. Kwiatkowski, V. Nikolaev, and J. Palomaki TyDi QA: a benchmark for information-seeking question answering in typologically diverse languages. Transactions of the Association for Computational Linguistics 8, p. 454–470. External Links: Link, Document Cited by: §C.1. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman Training verifiers to solve math word problems. External Links: 2110.14168, Link Cited by: §C.1. Conover et al. (2023) M. Conover, M. Hayes, A. Mathur, J. Xie, J. Wan, S. Shah, A. Ghodsi, P. Wendell, M. Zaharia, and R. Xin Free dolly: introducing the world’s first truly open instruction-tuned llm. External Links: Link Cited by: §5.1. Dai et al. (2026) Q. Dai, D. Zhang, J. W. Ma, and H. Peng Improving influence-based instruction tuning data selection for balanced learning of diverse capabilities. External Links: 2501.12147, Link Cited by: §1, §6. Gekhman et al. (2024) Z. Gekhman, G. Yona, R. Aharoni, M. Eyal, A. Feder, R. Reichart, and J. Herzig Does fine-tuning LLMs on new knowledge encourage hallucinations?. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 7765–7784. External Links: Link, Document Cited by: §1. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt Measuring massive multitask language understanding. External Links: 2009.03300, Link Cited by: §C.1. Hu et al. (2021) E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen LoRA: low-rank adaptation of large language models. External Links: 2106.09685, Link Cited by: §5.1. Ivison et al. (2025) H. Ivison, M. Zhang, F. Brahman, P. W. Koh, and P. Dasigi Large-scale data selection for instruction tuning. Note: arXiv preprint arXiv:2503.01807 External Links: 2503.01807, Document, Link Cited by: §5.1, §6. Jiang et al. (2023) A. Q. Jiang, A. Sablayrolles, A. Mensch, C. Bamford, D. S. Chaplot, D. de las Casas, F. Bressand, G. Lengyel, G. Lample, L. Saulnier, L. R. Lavaud, M. Lachaux, P. Stock, T. L. Scao, T. Lavril, T. Wang, T. Lacroix, and W. E. Sayed Mistral 7b. External Links: 2310.06825, Link Cited by: §5.1. Kandpal et al. (2023) N. Kandpal, H. Deng, A. Roberts, E. Wallace, and C. Raffel Large language models struggle to learn long-tail knowledge. In Proceedings of the 40th International Conference on Machine Learning, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett (Eds.), Proceedings of Machine Learning Research, Vol. 202, p. 15696–15707. External Links: Link Cited by: §1. Köpf et al. (2023) A. Köpf, Y. Kilcher, D. von Rütte, S. Anagnostidis, Z. R. Tam, K. Stevens, A. Barhoum, D. Nguyen, O. Stanley, R. Nagyfi, S. ES, S. Suri, D. Glushkov, A. Dantuluri, A. Maguire, C. Schuhmann, H. Nguyen, and A. Mattick OpenAssistant conversations - democratizing large language model alignment. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 47669–47681. External Links: Document, Link Cited by: §5.1. Li et al. (2026) B. Li, M. Wang, S. Zhang, and W. Ye Instruction data selection via answer divergence. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 4684–4702. Cited by: §5.1, §6. Li et al. (2024) M. Li, Y. Zhang, Z. Li, J. Chen, L. Chen, N. Cheng, J. Wang, T. Zhou, and J. Xiao From quantity to quality: boosting LLM performance with self-guided data selection for instruction tuning. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics, Cited by: §6. Lin et al. (2022) S. Lin, J. Hilton, and O. Evans TruthfulQA: measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, Cited by: §C.1. Liu et al. (2024a) L. Liu, X. Liu, D. F. Wong, D. Li, Z. Wang, B. Hu, and M. Zhang SelectIT: selective instruction tuning for LLMs via uncertainty-aware self-reflection. In Advances in Neural Information Processing Systems, Vol. 37. External Links: Link Cited by: §6. Liu et al. (2024b) W. Liu, W. Zeng, K. He, Y. Jiang, and J. He What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. External Links: 2312.15685, Link Cited by: §1, §5.1, §6. Liu et al. (2024c) Z. Liu, A. Karbasi, and T. Rekatsinas TSDS: data selection for task-specific model finetuning. In Advances in Neural Information Processing Systems, Vol. 37. External Links: Link Cited by: §5.1, §6. Longpre et al. (2023) S. Longpre, L. Hou, T. Vu, A. Webson, H. W. Chung, Y. Tay, D. Zhou, Q. V. Le, B. Zoph, J. Wei, and A. Roberts The flan collection: designing data and methods for effective instruction tuning. In Proceedings of the 40th International Conference on Machine Learning, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett (Eds.), Proceedings of Machine Learning Research, Vol. 202, p. 22631–22648. External Links: Link Cited by: §5.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §1. Qwen et al. (2024) Qwen, A. Yang, B. Yang, B. Zhang, B. Hui, et al. Qwen2.5 technical report. External Links: 2412.15115, Link Cited by: §5.1. Razeghi et al. (2022) Y. Razeghi, R. L. Logan IV, M. Gardner, and S. Singh Impact of pretraining term frequencies on few-shot numerical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2022, Y. Goldberg, Z. Kozareva, and Y. Zhang (Eds.), Abu Dhabi, United Arab Emirates, p. 840–854. External Links: Link, Document Cited by: §1. Suzgun et al. (2023) M. Suzgun, N. Scales, N. Schärli, S. Gehrmann, Y. Tay, H. W. Chung, A. Chowdhery, Q. V. Le, E. H. Chi, D. Zhou, and J. Wei Challenging BIG-bench tasks and whether chain-of-thought can solve them. In Findings of the Association for Computational Linguistics: ACL 2023, Cited by: §C.1. Taori et al. (2023) R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto Stanford alpaca: an instruction-following llama model. GitHub. Note: https://github.com/tatsu-lab/stanford_alpaca Cited by: §5.1. Xia et al. (2024) M. Xia, S. Malladi, S. Gururangan, S. Arora, and D. Chen LESS: selecting influential data for targeted instruction tuning. In International Conference on Machine Learning, Cited by: §1, §5.1, §6. Xu et al. (2024) C. Xu, Q. Sun, K. Zheng, X. Geng, P. Zhao, J. Feng, C. Tao, Q. Lin, and D. Jiang WizardLM: empowering large pre-trained language models to follow complex instructions. In International Conference on Learning Representations, B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (Eds.), Vol. 2024, p. 30745–30766. External Links: Link Cited by: §5.1. Yue et al. (2023) X. Yue, X. Qu, G. Zhang, Y. Fu, W. Huang, H. Sun, Y. Su, and W. Chen MAmmoTH: building math generalist models through hybrid instruction tuning. External Links: 2309.05653, Link Cited by: §1. Zhang et al. (2025) D. Zhang, Q. Dai, and H. Peng The best instruction-tuning data are those that fit. In Advances in Neural Information Processing Systems, Vol. 38. External Links: Document, Link Cited by: §6. Zhou et al. (2023) C. Zhou, P. Liu, P. Xu, S. Iyer, J. Sun, Y. Mao, X. Ma, A. Efrat, P. Yu, L. Yu, et al. LIMA: less is more for alignment. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §1, §6. Appendix A Details of Theoretical Analysis A.1 Assumptions We assume that the concept space Θ⊂ℝd ^d is compact and is equipped with a Borel probability reference measure λ with full support. The prior has a strictly positive continuous density π(θ)π(θ) with respect to λ. The input and output spaces are standard Borel spaces. There exists a common σ-finite measure ν on the output space such that each Pθ(⋅∣x)P_θ(· x) admits a density, denoted by Pθ(y∣x)P_θ(y x), with (θ,x,y)↦Pθ(y∣x)(θ,x,y) P_θ(y x) jointly measurable. Define P⋆(dx,dy)=PX(dx)Pθ⋆(dy∣x)P (dx,dy)=P_X(dx)P_θ (dy x), and assume that the SFT examples are i.i.d. from P⋆P . Let ℓθ(x,y)=logPθ(y∣x) _θ(x,y)= P_θ(y x) and Sn(θ)=∑i=1nℓθ(xi,yi)S_n(θ)= _i=1^n _θ(x_i,y_i). Assumption 1. There exists a measurable set 0Z_0 of P⋆P -probability one such that, for every (x,y)∈0(x,y) _0, ℓθ(x,y)∈ℝfor every θ∈Θ,supθ∈Θℓθ(x,y)<∞. _θ(x,y) every θ∈ , _θ∈ _θ(x,y)<∞. (16) Assumption 2 (Bounded log-likelihood ratios). For a fixed r>0r>0, there exists Mr∈(0,∞)M_r∈(0,∞) such that, for every (x,y)∈0(x,y) _0 and every θ∈Arθ∈ A_r, |ℓθ(x,y)−ℓθ⋆(x,y)|≤Mr. | _θ(x,y)- _θ (x,y) |≤ M_r. (17) Assumption 3. For a fixed r>0r>0, there exists Lr∈(0,∞)L_r∈(0,∞) such that, for every (x,y)∈0(x,y) _0, |ℓθ(x,y)−ℓθ′(x,y)| | _θ(x,y)- _θ (x,y)| ≤Lr‖θ−θ′‖, ≤ L_r\|θ-θ \|, θ,θ′∈Ar, θ,θ ∈ A_r, (18) |ℓθ(x,y)−ℓθ⋆(x,y)| | _θ(x,y)- _θ (x,y)| ≤Lr‖θ−θ⋆‖, ≤ L_r\|θ-θ \|, ‖θ−θ⋆‖<r/2. \|θ-θ \|<r/2. (19) Assumption 4. The local approximation term α(r)α(r) is finite, and the pointwise supremum used to define it is measurable. For posterior concentration, define ρr=minr2,ϵ(r)8Lr,Ur=θ∈Θ:‖θ−θ⋆‖<ρr, _r= \ r2, ε(r)8L_r \, U_r=\θ∈ :\|θ-θ \|< _r\, (20) and let m(r)=∫Urπ(θ)π(θ⋆)λ(θ).m(r)= _U_r π(θ)π(θ )\,λ(dθ). (21) Because ρr>0 _r>0, λ has full support, and π is strictly positive and continuous, m(r)>0m(r)>0. Let r=N(Ar,ϵ(r)8Lr,∥⋅∥)N_r=N (A_r, ε(r)8L_r,\|·\| ) (22) be the covering number of ArA_r. Compactness of ArA_r implies r<∞N_r<∞. For η∈(0,1)η∈(0,1), define nsep(r,η)=8Mr2ϵ(r)2log(rη).n_sep(r,η)= 8M_r^2ε(r)^2 ( N_rη ). (23) Finally, let Δn(θ)=Sn(θ)−Sn(θ⋆). _n(θ)=S_n(θ)-S_n(θ ). (24) A.2 Proof of Theorem 1 Proof. We first establish a uniform empirical separation over ArA_r. For any fixed θ∈Arθ∈ A_r, define Zi(θ)=ℓθ(xi,yi)−ℓθ⋆(xi,yi).Z_i(θ)= _θ(x_i,y_i)- _θ (x_i,y_i). By Assumption 2, Zi(θ)∈[−Mr,Mr]Z_i(θ)∈[-M_r,M_r], while the definition of ϵ(r)ε(r) gives Zi(θ)=−K(θ)≤−ϵ(r).EZ_i(θ)=-K(θ)≤-ε(r). Hence, Δn(θ)≥−nϵ(r)2⊆Δn(θ)−Δn(θ)≥nϵ(r)2. \ _n(θ)≥- nε(r)2 \ \ _n(θ)-E _n(θ)≥ nε(r)2 \. Hoeffding’s inequality yields PrΔn(θ)≥−nϵ(r)2≤exp(−nϵ(r)28Mr2). \ _n(θ)≥- nε(r)2 \≤ (- nε(r)^28M_r^2 ). (25) Choose a cover r⊂ArC_r⊂ A_r with |r|=r|C_r|=N_r and radius ϵ(r)/(8Lr)ε(r)/(8L_r). By a union bound, Pr∃θc∈r:Δn(θc)≥−nϵ(r)2≤rexp(−nϵ(r)28Mr2). \∃ _c _r: _n( _c)≥- nε(r)2 \ _r (- nε(r)^28M_r^2 ). When n≥nsep(r,η)n≥ n_sep(r,η), the right-hand side is at most η. On the complementary event, every θ∈Arθ∈ A_r has a center θc∈r _c _r such that, by Assumption 3, |Δn(θ)−Δn(θc)|≤∑i=1nLr‖θ−θc‖≤nϵ(r)8.| _n(θ)- _n( _c)|≤ _i=1^nL_r\|θ- _c\|≤ nε(r)8. Therefore, with probability at least 1−η1-η, supθ∈ArΔn(θ)≤−3nϵ(r)8≤−nϵ(r)4. _θ∈ A_r _n(θ)≤- 3nε(r)8≤- nε(r)4. (26) On this event, the posterior mass of ArA_r can be written as qn⋆(Ar)=∫Arexp(Δn(θ))π(θ)π(θ⋆)λ(θ)∫Θexp(Δn(θ))π(θ)π(θ⋆)λ(θ).q_n (A_r)= _A_r ( _n(θ) ) π(θ)π(θ )λ(dθ) _ ( _n(θ) ) π(θ)π(θ )λ(dθ). (27) For every θ∈Arθ∈ A_r, logπ(θ)π(θ⋆)+Δn(θ)≤B(r)−nϵ(r)4. π(θ)π(θ )+ _n(θ)≤ B(r)- nε(r)4. Since λ(Ar)≤1λ(A_r)≤ 1, the numerator of 27 satisfies ∫Arexp(Δn(θ))π(θ)π(θ⋆)λ(θ)≤exp(B(r)−nϵ(r)4). _A_r ( _n(θ) ) π(θ)π(θ )λ(dθ)≤ (B(r)- nε(r)4 ). (28) For every θ∈Urθ∈ U_r, Assumption 3 and the definition of ρr _r imply Δn(θ)≥−∑i=1n|ℓθ(xi,yi)−ℓθ⋆(xi,yi)|≥−nϵ(r)8. _n(θ)≥- _i=1^n| _θ(x_i,y_i)- _θ (x_i,y_i)|≥- nε(r)8. Restricting the denominator of 27 to UrU_r gives ∫Θexp(Δn(θ))π(θ)π(θ⋆)λ(θ)≥m(r)exp(−nϵ(r)8). _ ( _n(θ) ) π(θ)π(θ )λ(dθ)≥ m(r) (- nε(r)8 ). (29) Combining 28 and 29, qn⋆(Ar)≤1m(r)exp(B(r)−nϵ(r)8).q_n (A_r)≤ 1m(r) (B(r)- nε(r)8 ). Together with qn⋆(Ar)≤1q_n (A_r)≤ 1, we obtain qn⋆(Ar)≤min1,1m(r)exp(B(r)−nϵ(r)8).q_n (A_r)≤ \1, 1m(r) (B(r)- nε(r)8 ) \. This completes the proof. ∎ A.3 Proof of Corollary 1 Proof. In the head case, B(r)≤0B(r)≤ 0, so the posterior concentration bound becomes qn⋆(Ar)≤min1,1m(r)exp(−nϵ(r)8).q_n (A_r)≤ \1, 1m(r) (- nε(r)8 ) \. To guarantee qn⋆(Ar)≤δq_n (A_r)≤δ, it is sufficient that 1m(r)exp(−nϵ(r)8)≤δ, 1m(r) (- nε(r)8 )≤δ, which gives n≥8ϵ(r)(log1m(r)δ)+.n≥ 8ε(r) ( 1m(r)δ )_+. In the tail case, B(r)>0B(r)>0, and it is sufficient that 1m(r)exp(B(r)−nϵ(r)8)≤δ. 1m(r) (B(r)- nε(r)8 )≤δ. Rearranging gives n≥8ϵ(r)(B(r)+log1m(r)δ)+.n≥ 8ε(r) (B(r)+ 1m(r)δ )_+. This completes the proof. ∎ A.4 Proof of Theorem 2 Proof. Fix an SFT dataset nD_n. For PXP_X-almost every x, convexity of KL divergence in its second argument gives DKL(Pθ⋆(⋅∣x)∥Pqn⋆(⋅∣x)) D_KL (P_θ (· x)\|P_q_n (· x) ) (30) ≤∫ΘDKL(Pθ⋆(⋅∣x)∥Pθ(⋅∣x))qn⋆(dθ). ≤ _ D_KL (P_θ (· x)\|P_θ(· x) )q_n (dθ). (31) Splitting the integral over Θ∖Ar A_r and ArA_r, the contribution from Θ∖Ar A_r is bounded by the local approximation term α(r)α(r). For θ∈Arθ∈ A_r, Assumption 2 implies DKL(Pθ⋆(⋅∣x)∥Pθ(⋅∣x))=y∼Pθ⋆(⋅∣x)[ℓθ⋆(x,y)−ℓθ(x,y)]≤Mr.D_KL (P_θ (· x)\|P_θ(· x) )=E_y P_θ (· x) [ _θ (x,y)- _θ(x,y) ]≤ M_r. Taking expectation over x therefore gives ℰn≤α(r)+Mrqn⋆(Ar).E_n≤α(r)+M_rq_n (A_r). Under the conditions of Theorem 1, with probability at least 1−η1-η, qn⋆(Ar)≤min1,1m(r)exp(B(r)−nϵ(r)8).q_n (A_r)≤ \1, 1m(r) (B(r)- nε(r)8 ) \. Substituting this bound yields ℰn≤α(r)+Mrmin1,1m(r)exp(B(r)−nϵ(r)8).E_n≤α(r)+M_r \1, 1m(r) (B(r)- nε(r)8 ) \. This completes the proof. ∎ Appendix B Pseudo Code Algorithm 1 PASS: Prior-barrier Aware SFT Instruction Selection 1: Candidate pool D, reference set T, pretrained model M0M_0, selection budget n 2: Selected subset nD_n with |n|=n|D_n|=n 3: M1: Distinguishing Evidence Estimation 4: for all (x,y)∈(x,y) do 5: Encode (x,y)(x,y) with M0M_0 to obtain the response representation z(x,y)z(x,y) 6: end for 7: Hierarchically cluster the reference representations using the coherence criterion 8: Obtain target concepts Θ=θ1,…,θC =\ _1,…, _C\ and their reference subsets θ∈Θ\T_θ\_θ∈ 9: for all θ∈Θθ∈ do 10: Compute the desired representation pθp_θ from θT_θ 11: Collect wrong-response instructions associated with θ 12: Construct the competing representations θ=nθ1,…,nθKθN_θ=\n_θ 1,…,n_θ K_θ\ 13: end for 14: for all (xi,yi)∈(x_i,y_i) do 15: Encode (xi,yi)(x_i,y_i) to obtain zi=z(xi,yi)z_i=z(x_i,y_i) 16: for all θ∈Θθ∈ do 17: Compute sθ+(zi)s_θ^+(z_i) and sθ−(zi)s_θ^-(z_i) using Eq. 9 18: Compute distinguishing evidence ϵiθ _iθ using Eq. 10 19: end for 20: end for 21: Form the evidence matrix [ϵiθ]∈ℝN×C[ _iθ] ^N× C 22: M2: Barrier-Aware Instruction Allocation 23: for all θ∈Θθ∈ do 24: for all (x,y)∈θ(x,y) _θ do 25: Generate y^∼M0(⋅∣x) y M_0(· x) and obtain z^=z(x,y^) z=z(x, y) 26: end for 27: Compute the prior barrier BθB_θ using Eq. 11 28: Compute the existing target-concept support γθ _θ using Eq. 12 29: end for 30: Compute the allocation weights Aθ∈Θ\A_θ\_θ∈ using Eq. 13 31: Initialize ←∅S← 32: while ||<n|S|<n do 33: for all θ∈Θθ∈ do 34: Compute Rθ+()R_θ^+(S) and Rθ−()R_θ^-(S) 35: end for 36: Compute the redundancy term D()D(S) 37: Evaluate the selection objective F()F(S) using Eq. 14 38: Select i⋆i by the marginal-gain rule in Eq. 15 39: ←∪(xi⋆,yi⋆)S ∪\(x_i ,y_i )\ 40: end while 41: return n←D_n Appendix C Details of Experiments C.1 Implementation Details We evaluate the five capabilities in the downstream task using MMLU [Hendrycks et al., 2021], BBH [Suzgun et al., 2023], GSM8K [Cobbe et al., 2021], TruthfulQA [Lin et al., 2022], and TyDiQA [Clark et al., 2020], respectively. Following prior work, each capability benchmark is partitioned into 20%20\% reference data and 80%80\% evaluation data. The reference partitions from all five benchmarks are combined into a single reference set T representing the desired behaviors of the downstream task, while the remaining examples are used for evaluation. The resulting evaluation sets contain 11,25011,250, 1,0801,080, 200200, 632632, and 885885 examples for MMLU, BBH, GSM8K, TruthfulQA, and TyDiQA, respectively. All experiments are conducted on NVIDIA A100 GPUs with 80GB memory. C.2 Runtime and Memory Consumption Figure 4 summarizes the total runtime and peak memory usage during instruction selection. As shown, LESS, TSDS, and ADG incur substantially higher running time, while our method requires considerably less time. Our method has the lowest CPU memory usage among the non-random selectors and comparable GPU memory usage. Figure 4: Runtime and memory consumption of all selection methods. (a) Total runtime in minutes. (b) Peak CPU memory. (c) Peak GPU memory per device. C.3 Selection Composition Figures 6 and 6 compare the source distributions of the instructions selected under the 5,0005,000 budget. Random selection largely preserves the original pool distribution, whereas PASS substantially reweights the source mixture. On both Mistral-7B and Qwen2.5-7B, PASS increases the proportions of FLAN V2, OASST1, and Dolly while reducing the proportion of WizardLM relative to the candidate pool. The selected distributions also vary across the two backbones, reflecting the model-dependent nature of the prior barrier and instruction evidence used by PASS. In contrast, several baselines exhibit much stronger concentration on a small number of sources, such as TADS and TSDS. These results suggest that PASS adapts the composition of the selected subset rather than simply preserving the source distribution or concentrating on a single source. Figure 5: Distribution of instructions selected by Mistral-7B under the 5K selection budget. Figure 6: Distribution of instructions selected by Qwen2.5-7B under the 5K selection budget.