Introduction
Supervised fine-tuning (SFT) on a mixture of instruction datasets shapes much of a language model’s reasoning and problem-solving ability. With a fixed training budget and pools of hundreds of tasks, the central design choice is which tasks to include and how much of the budget each receives . Common practice relies on uniform sampling, dataset-size weighting [8 ] , or hand-crafted rules, which can let dominant sources take over the mixture and spend budget on redundant tasks. Automated methods such as submodular selection (SMART; RBR24), influence-based retrieval (LESS, XMG+24; BIDS, DZMP25) and proxy-based mixture prediction (RegMix, LZM+24; Data Mixing Laws, LLX25) typically select discrete subsets rather than continuous proportions, rely on semantic or per-example scores that do not capture cross-task transfer, or require repeated training runs.
How can we automatically choose an SFT task mixture that is simultaneously representative and diverse, and that reliably improves downstream performance under a fixed budget?
We introduce TaskMixPGM (Task Mixtures via Probabilistic Graphical Modelling ), which models the task pool as a dense Markov random field: unary potentials reward representative tasks and pairwise potentials penalize redundant ones. Both are computed from behavioral similarity, by comparing the predictions of single-task fine-tuned models, rather than from metadata or embeddings. The learned weights also show which tasks act as broad “attractors” and which are specialized, and for budgeted selection we show that the induced set function is weakly submodular, so greedy construction comes with approximation guarantees.
Q1. Can functional, behavior-based task affinities be used to compute continuous mixture proportions that outperform strong heuristic and selection baselines?
Q2. Does the resulting mixture optimization yield interpretable structure (task clusters, redundancy, and influential “attractor” tasks) and support efficient budgeted construction?
Contributions. Our main contributions are as follows:
An energy model over behavioral task affinities. We cast SFT mixture design as energy minimization over tasks, with affinities measured from how single-task models predict each other’s data.
Guarantees for budgeted task selection. We show that the induced set function is monotone and weakly submodular, so greedy task selection has an approximation guarantee.
Insight into what drives the mixture. We characterize how much spectral shift convexity actually requires, and show that the mixture favors broadly transferable tasks.
A single, benchmark-independent mixture. Computed once, the same mixture outperforms heuristic and selection baselines across three model families across different budgets on state-of-the-art benchmarks.
Preliminaries and Background work
Notation. We write [ n ] : = { 1 , … , n } [n] := \{1,\ldots,n\} [ n ] := { 1 , … , n } and R + n \mathbb{R}_{+}^{n} R + n for the non-negative orthant. Vectors are lower-case bold (x \boldsymbol{x} x ) and matrices upper-case bold (X \boldsymbol{X} X ), with individual entries denoted as x [ i ] x_{[i]} x [ i ] and X [ i j ] X_{[ij]} X [ ij ] . x [ i : j ] x_{[i:j]} x [ i : j ] denotes the subvector with indices i , … , j − 1 i,\ldots,j-1 i , … , j − 1 , and x [ : j ] : = x [ 0 : j ] x_{[:j]} := x_{[0:j]} x [ : j ] := x [ 0 : j ] . 1 n \mathbf{1}_{n} 1 n , 1 m × n \mathbf{1}_{m\times n} 1 m × n and I \mathbf{I} I are the all-ones vector, the all-ones matrix and the identity. Δ n : = { x ∈ R + n : ∑ i x [ i ] = 1 } \Delta_{n} := \{x \in\mathbb{R}_{+}^{n} : \sum_i x_{[i]} = 1\} Δ n := { x ∈ R + n : ∑ i x [ i ] = 1 } denotes the probability simplex, and ( a ) + : = max { a , 0 } (a)_{+} := \max\{a,0\} ( a ) + := max { a , 0 } . For μ , ν ∈ Δ n \mu,\nu\in\Delta_n μ , ν ∈ Δ n , KL ( μ ∥ ν ) : = ∑ i μ [ i ] log ( μ [ i ] / ν [ i ] ) \operatorname{KL}(\mu\parallel\nu) := \sum_i \mu_{[i]} \log(\mu_{[i]}/\nu_{[i]}) KL ( μ ∥ ν ) := ∑ i μ [ i ] log ( μ [ i ] / ν [ i ] ) denotes the Kullback–Leibler divergence, assuming ν [ i ] > 0 \nu_{[i]} > 0 ν [ i ] > 0 whenever μ [ i ] > 0 \mu_{[i]} > 0 μ [ i ] > 0 . For symmetric matrix X \boldsymbol{X} X , λ min ( X ) \lambda_{\min}(\boldsymbol{X}) λ m i n ( X ) and λ max ( X ) \lambda_{\max}(\boldsymbol{X}) λ m a x ( X ) are its extreme eigenvalues, and for X ≻ 0 \boldsymbol{X} \succ0 X ≻ 0 , κ ( X ) : = λ max ( X ) / λ min ( X ) \kappa(\boldsymbol{X}) := \lambda_{\max}(\boldsymbol{X})/\lambda_{\min}(\boldsymbol{X}) κ ( X ) := λ m a x ( X ) / λ m i n ( X ) is its condition number. We write X ⪰ 0 \boldsymbol{X} \succeq0 X ⪰ 0 for a positive semi-definite (PSD) matrix and X ⋡ 0 \boldsymbol{X} \nsucceq0 X ⋡ 0 else.
Further, let 1 = ( 1 , … , 1 ) ⊤ ∈ R n \mathbf{1} = (1,\ldots,1)^{\top} \in\mathbb{R}^{n} 1 = ( 1 , … , 1 ) ⊤ ∈ R n denote the all-ones vector, and 1 ⊥ = { h ∈ R n : 1 ⊤ h = 0 } \mathbf{1}^{\perp} = \{h \in\mathbb{R}^{n} : \mathbf{1}^{\top}h = 0\} 1 ⊥ = { h ∈ R n : 1 ⊤ h = 0 } be its orthogonal complement: the vectors whose entries sum to zero. If p , p ′ ∈ Δ n p,p' \in\Delta_n p , p ′ ∈ Δ n , then 1 ⊤ ( p ′ − p ) = 1 − 1 = 0 \mathbf{1}^{\top}(p' - p) = 1 - 1 = 0 1 ⊤ ( p ′ − p ) = 1 − 1 = 0 , so p ′ − p ∈ 1 ⊥ p' - p \in\mathbf{1}^{\perp} p ′ − p ∈ 1 ⊥ .
Submodularity ratio. Let f : 2 V → R f : 2^{\mathcal{V}} \to\mathbb{R} f : 2 V → R be a set function over ground set V \mathcal{V} V . For any subset S ⊆ V S \subseteq\mathcal{V} S ⊆ V and element e ∈ V ∖ S e \in\mathcal{V} \setminus S e ∈ V ∖ S , the marginal gain is Δ f ( e ∣ S ) = f ( S ∪ { e } ) − f ( S ) \Delta f(e \mid S) = f(S \cup\{e\}) - f(S) Δ f ( e ∣ S ) = f ( S ∪ { e }) − f ( S ) . The function f f f is submodular if Δ f ( e ∣ A ) ≥ Δ f ( e ∣ B ) \Delta f(e \mid A) \geq\Delta f(e \mid B) Δ f ( e ∣ A ) ≥ Δ f ( e ∣ B ) for all A ⊆ B ⊆ V A \subseteq B \subseteq\mathcal{V} A ⊆ B ⊆ V and e ∉ B e \notin B e ∈ / B . The submodularity ratio [12 ] captures how close a non-submodular function is to being submodular:
γ L , κ ( f ) = min S ⊆ L , A ⊆ V ∣ A ∣ ≤ κ , A ∩ S = ∅ ∑ u ∈ A Δ f ( u ∣ S ) f ( S ∪ A ) − f ( S ) . (1) \gamma_{\mathcal{L},\kappa}(f) = \min_{\substack{S \subseteq\mathcal{L},\ A \subseteq\mathcal{V}\\ |A|\leq\kappa,\ A\cap S=\varnothing}} \frac{\sum_{u\in A}\Delta f(u\mid S)}{f(S\cup A)-f(S)}. \tag*{(1)} γ L , κ ( f ) = S ⊆ L , A ⊆ V ∣ A ∣ ≤ κ , A ∩ S = ∅ min f ( S ∪ A ) − f ( S ) ∑ u ∈ A Δ f ( u ∣ S ) . (1)
with 0 / 0 : = 1 0/0 := 1 0/0 := 1 . If γ > 0 \gamma> 0 γ > 0 , the greedy algorithm for max ∣ S ∣ ≤ κ f ( S ) \max_{|S|\leq\kappa} f(S) max ∣ S ∣ ≤ κ f ( S ) achieves a ( 1 − e − γ ) (1-e^{-\gamma}) ( 1 − e − γ ) approximation to the optimum [31 , 12 ] .
RSC and RSM. A differentiable function l : R d → R l : \mathbb{R}^{d} \to\mathbb{R} l : R d → R is restricted strong concave (RSC) with parameter c Ω c_{\Omega} c Ω and restricted smooth (RSM) with parameter C Ω C_{\Omega} C Ω on a domain Ω ⊆ R d × R d \Omega\subseteq\mathbb{R}^{d}\times\mathbb{R}^{d} Ω ⊆ R d × R d if ∀ ( x , y ) ∈ Ω \forall(\boldsymbol{x},\boldsymbol{y})\in\Omega ∀ ( x , y ) ∈ Ω ,
l ( x ) − l ( y ) + ⟨ ∇ l ( x ) , y − x ⟩ ∈ [ c Ω 2 ∥ y − x ∥ 2 2 , C Ω 2 ∥ y − x ∥ 2 2 ] . l(\boldsymbol{x}) - l(\boldsymbol{y}) + \langle\nabla l(\boldsymbol{x}),\boldsymbol{y}-\boldsymbol{x}\rangle\in\left[\frac{c_{\Omega}}{2}\|\boldsymbol{y}-\boldsymbol{x}\|_{2}^{2},\frac{C_{\Omega}}{2}\|\boldsymbol{y}-\boldsymbol{x}\|_{2}^{2}\right]. l ( x ) − l ( y ) + ⟨ ∇ l ( x ) , y − x ⟩ ∈ [ 2 c Ω ∥ y − x ∥ 2 2 , 2 C Ω ∥ y − x ∥ 2 2 ] .
RSC and RSM have been studied in the context of weakly submodular functions [15 , 17 ] . Let Ω κ : = { ( x , y ) : ∥ x ∥ 0 ≤ κ , ∥ y ∥ 0 ≤ κ , x , y ≥ 0 } \Omega_{\kappa} := \{(\boldsymbol{x},\boldsymbol{y}) : \|\boldsymbol{x}\|_{0} \leq\kappa,\ \|\boldsymbol{y}\|_{0} \leq\kappa,\ \boldsymbol{x},\boldsymbol{y} \geq0\} Ω κ := {( x , y ) : ∥ x ∥ 0 ≤ κ , ∥ y ∥ 0 ≤ κ , x , y ≥ 0 } , and let c κ c_{\kappa} c κ and C κ C_{\kappa} C κ denote the RSC and RSM parameters of l l l on Ω κ \Omega_{\kappa} Ω κ . Since Ω k ⊆ Ω κ \Omega_k \subseteq\Omega_{\kappa} Ω k ⊆ Ω κ whenever k ≤ κ k \leq\kappa k ≤ κ , it is easily verified that c k ≥ c κ c_k \geq c_{\kappa} c k ≥ c κ and C k ≤ C κ C_k \leq C_{\kappa} C k ≤ C κ . Finally, define Ω ^ : = { ( x , y ) : ∥ x − y ∥ 0 ≤ 1 } \widehat{\Omega}:=\{(x,y):\|x-y\|_0\leq1\} Ω := {( x , y ) : ∥ x − y ∥ 0 ≤ 1 } , with associated smoothness parameter C ~ 1 \widetilde{C}_1 C 1 .
Related Work. Choosing the right mixture of training data is central to efficient LLM fine-tuning, whether the goal is a specific task or broad generalization. Early work measured task similarity with Maximum Mean Discrepancy or reconstruction error to retrieve examples [2 , 19 , 3 ] ; more recent work represents tasks by lightweight LoRA adapters and uses low-rank similarity to guide transfer [22 ] .
A second line of work estimates the influence of individual examples on a target task. Influence functions [20 ] are accurate but expensive, so cheaper proxies track forgotten examples [41 ] or gradient norms [PGD21]. For instruction tuning, LESS [49 ] retrieves examples whose low-rank gradient features match the target, and BIDS [14 ] normalizes these scores per task to avoid favoring high-gradient tasks.
Other work targets diversity and coverage, combining difficulty scores with clustering [52 , 30 ] or selecting coresets that approximate full training dynamics [36 , 24 ] . For multi-task instruction tuning, SMART [35 ] allocates the budget across tasks with a submodular objective and selects non-redundant examples. Because scoring every example on a large model is costly, STAFF [53 ] scores with a smaller sibling model first, TSDS [26 ] uses optimal transport for scalable distribution matching, and DELIFT [1 ] scores examples by their usefulness as in-context prompts for one another. See Section H for additional related work on data mixture optimisation and task-affinity-based reweighting.
Contextualizing our framework. These methods rank data by scalar relevance scores, either per instance [49 , 14 ] or per dataset [2 , 22 ] , and do not model redundancy between tasks. We instead pose mixture selection as optimization over an energy landscape of pairwise task interactions, encoded in a symmetric affinity matrix S S S estimated from the predictive behavior of single-task models.
Proposed Approach
Problem setup. We consider a set of n n n instruction tuning tasks V : = { T 1 , … , T n } \mathcal{V}:=\{\mathcal{T}_1,\ldots,\mathcal{T}_n\} V := { T 1 , … , T n } , where each task T i \mathcal{T}_i T i is associated with a corresponding dataset D i \mathcal{D}_i D i . Typically we consider supervised finetuning instruction dataset of the form D i = { x i , y i } i = 1 n \mathcal{D}_i=\{x_i,y_i\}_{i=1}^{n} D i = { x i , y i } i = 1 n where each x i x_i x i is an input sequence and y i y_i y i is the corresponding output.
Our goal is to learn a sampling distribution p ∗ ∈ Δ n \mathbf{p}^* \in\Delta^n p ∗ ∈ Δ n over n n n such tasks, which determines how training effort can be distributed across the collection of tasks.
Redundancy and structure across tasks. Tasks in a training pool are neither independent nor equally informative. Redundancy can arise from overlapping datasets across collections, such as BoolQ , RTE , and COPA appearing in both FLAN [25 ] and SuperGLUE [45 ] , from multiple prompt variants of the same dataset in T0 [39 ] , or from tasks targeting similar capabilities, such as MNLI , SNLI , and ANLI for natural language inference. In contrast, tasks such as Evol-CodeAlpaca for code generation, NuminaMath-TIR for mathematical reasoning, and Aya [SVD+24] for multilingual instruction following provide complementary coverage. Existing mixture methods often optimize tasks within predefined groups or relative to a fixed target [35 , 26 ] , which can miss these interactions. A task that is redundant in one mixture may be useful in another because of the other tasks selected. This motivates modeling the task pool jointly to account for redundancy, complementarity, and cross-task effects when allocating the training budget.
Cross-task Similarity. We collect pairwise task affinities in a symmetric matrix S ∈ R n × n S \in\mathbb{R}^{n \times n} S ∈ R n × n , where S [ i j ] S_{[ij]} S [ ij ] measures how related T i \mathcal{T}_i T i and T j \mathcal{T}_j T j are (defined in Equation (5) ). The degree S [ i ] : = ∑ j S [ i j ] S_{[i]}:=\sum_j S_{[ij]} S [ i ] := ∑ j S [ ij ] summarizes how strongly T i \mathcal{T}_i T i relates to the pool as a whole: tasks with larger degree share more structure with other tasks, while tasks with smaller degree are more specialized.
Figure 1. Illustrative example. Left: a six-task MRF whose edges are labelled with similarities S i j S_{ij} S ij (thicker edges for high S i j S_{ij} S ij , dashed for low). Right: the optimal mixture p ∗ \mathbf{p}^{*} p ∗ from Eq. (3) for these similarities; darker shading marks larger weight in both panels. The most connected task T 6 \mathcal{T}_{6} T 6 receives the most mass, while the strongly redundant pairs (T 1 , T 2 \mathcal{T}_{1},\mathcal{T}_{2} T 1 , T 2 and T 4 , T 5 \mathcal{T}_{4},\mathcal{T}_{5} T 4 , T 5 , both with S i j = 0.8 S_{ij}=0.8 S ij = 0.8 ) split theirs.
Energy-based modelling. We model the task pool as a dense Markov random field (MRF) [21 , 43 ] : each node is a task, and the edge weight S i j S_{ij} S ij is the affinity between tasks T i \mathcal{T}_{i} T i and T j \mathcal{T}_{j} T j . Modelling all tasks jointly lets the mixture account for coverage and redundancy at once: broadly connected tasks gain weight, while highly similar tasks compete for probability mass. We write ξ n = { T i } i = 1 n \xi_n=\{\mathcal{T}_i\}_{i=1}^{n} ξ n = { T i } i = 1 n for the resulting assignment of a sampling weight to each task.
Task Selection via Energy-Based Model
Each task receives a unary potential proportional to its degree, Ψ u n : = β S 1 \boldsymbol{\Psi}_{\mathrm{un}}:=\beta S\mathbf{1} Ψ un := β S 1 (so Ψ u n [ i ] = β S [ i ] \boldsymbol{\Psi}_{\mathrm{un}}[i]=\beta S[i] Ψ un [ i ] = β S [ i ] ), and each pair of tasks a pairwise potential proportional to their affinity, Ψ p a i r : = λ S \boldsymbol{\Psi}_{\mathrm{pair}}:=\lambda S Ψ pair := λ S , where β , λ > 0 \beta,\lambda>0 β , λ > 0 set the strength of each term. The energy of a mixture p ∈ Δ n \mathbf{p}\in\Delta_n p ∈ Δ n is
max p ∈ Δ n E ( p ) = ∑ i = 1 n Ψ u n [ i ] p [ i ] − 1 2 ∑ i = 1 n ∑ j = 1 n Ψ p a i r [ i j ] p [ i ] p [ j ] = Ψ u n T p − 1 2 p T Ψ p a i r p . (2) \max_{\mathbf{p}\in\Delta_n}\ E(\mathbf{p})=\sum_{i=1}^{n}\boldsymbol{\Psi}_{\mathrm{un}}[i]\mathbf{p}[i]-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\boldsymbol{\Psi}_{\mathrm{pair}}[ij]\mathbf{p}[i]\mathbf{p}[j]
=\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p}-\frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p}. \tag*{(2)} p ∈ Δ n max E ( p ) = i = 1 ∑ n Ψ un [ i ] p [ i ] − 2 1 i = 1 ∑ n j = 1 ∑ n Ψ pair [ ij ] p [ i ] p [ j ] = Ψ un T p − 2 1 p T Ψ pair p . (2)
The first term rewards representative tasks, those with high total affinity to the pool; the second penalizes placing mass on similar pairs , which promotes diversity. Equivalently, we minimize E ^ ( p ) : = − E ( p ) \hat{E}(\mathbf{p}):=-E(\mathbf{p}) E ^ ( p ) := − E ( p ) :
min p ∈ Δ n E ^ ( p ) = − Ψ u n T p + 1 2 p T Ψ p a i r p . (3) \min_{\mathbf{p}\in\Delta_n}\ \hat{E}(\mathbf{p})=-\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p}+\frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p}. \tag*{(3)} p ∈ Δ n min E ^ ( p ) = − Ψ un T p + 2 1 p T Ψ pair p . (3)
Dividing by λ \lambda λ does not change the minimizer, so it depends only on the ratio ρ : = β / λ \rho:=\beta/\lambda ρ := β / λ : larger ρ \rho ρ favors high-degree tasks, smaller ρ \rho ρ weights redundancy more heavily. Section C.2 shows that the minimizer is the projection of the scaled uniform allocation ρ 1 \rho\mathbf{1} ρ 1 onto the simplex in the geometry of task affinities, and Section C.4 explains how ρ \rho ρ controls coverage.
When is the objective convex? If Ψ p a i r ⪰ 0 \boldsymbol{\Psi}_{\mathrm{pair}}\succeq0 Ψ pair ⪰ 0 , Equation (3) is a convex quadratic program over the simplex and can be solved with standard methods such as projected gradient descent (PGD; [46 Chapter 7] ) or entropic mirror descent [4 ] . PGD then converges to the global optimum at rate O ( 1 / t ) O(1/t) O ( 1/ t ) with constant step size η < 1 / L \eta<1/L η < 1/ L , where L = λ max ( Ψ p a i r ) L=\lambda_{\max}(\boldsymbol{\Psi}_{\mathrm{pair}}) L = λ m a x ( Ψ pair ) is the Lipschitz constant of the gradient; pseudocode is given in Algorithm 1.
Non-convexity of the objective. Strictly, PGD needs Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair to be positive semidefinite only on the directions the simplex allows. As we show next, the affinity matrix in our setting does not satisfy even this weaker condition, so we modify the objective to restore convexity.
Non-PSD Correction via Spectrum Shifting. When the pairwise similarity matrix Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair is not positive semidefinite (PSD), i.e., Ψ p a i r ⪰̸ 0 \boldsymbol{\Psi}_{\mathrm{pair}}\not\succeq0 Ψ pair ⪰ 0 , the resulting optimization problem is no longer convex. To restore convexity, we apply a spectrum-shifting correction [6 , 42 ] to obtain a positive semidefinite matrix.
A common way to restore convexity while maintaining a positive spectral margin is to shift the spectrum of Ψ p a i r \mathbf{\Psi}_{\mathrm{pair}} Ψ pair so that its smallest eigenvalue is at least a small constant ϵ > 0 \epsilon>0 ϵ > 0 , i.e., Ψ p a i r ⪰ ϵ I : = Ψ p a i r + ( ϵ − λ min ( Ψ p a i r ) ) + I \mathbf{\Psi}_{\mathrm{pair}}^{\succeq\epsilon I}:=\mathbf{\Psi}_{\mathrm{pair}}+(\epsilon-\lambda_{\min}(\mathbf{\Psi}_{\mathrm{pair}}))_{+}I Ψ pair ⪰ ϵ I := Ψ pair + ( ϵ − λ m i n ( Ψ pair ) ) + I . This correction ensures λ min ( Ψ p a i r ⪰ ϵ I ) ≥ ϵ \lambda_{\min}(\mathbf{\Psi}_{\mathrm{pair}}^{\succeq\epsilon I})\ge\epsilon λ m i n ( Ψ pair ⪰ ϵ I ) ≥ ϵ , thereby yielding a positive-definite quadratic objective. However, the shift also modifies the original objective by introducing the additional isotropic regularization term ( ϵ − λ min ( Ψ p a i r ) ) + ∥ p ∥ 2 2 (\epsilon-\lambda_{\min}(\mathbf{\Psi}_{\mathrm{pair}}))_{+}\lVert\mathbf{p}\rVert_{2}^{2} ( ϵ − λ m i n ( Ψ pair ) ) + ∥ p ∥ 2 2 . We read this shift as restoring the self-affinity that the hollow matrix S S S leaves out, and discuss how large it needs to be in Section C.3.
Critical shift τ c \tau_c τ c . Any two learnt mixtures p , p ′ ∈ Δ n \mathbf{p},\mathbf{p}'\in\Delta_n p , p ′ ∈ Δ n differ by h = p ′ − p ∈ 1 ⊥ \mathbf{h}=\mathbf{p}'-\mathbf{p}\in\mathbf{1}^{\perp} h = p ′ − p ∈ 1 ⊥ , so E ^ ( ⋅ ) \hat{E}(\cdot) E ^ ( ⋅ ) is strictly convex on Δ n \Delta_n Δ n if and only if h ⊤ ( S + τ I ) h > 0 \mathbf{h}^{\top}(S+\tau I)\mathbf{h}>0 h ⊤ ( S + τ I ) h > 0 for all nonzero h ∈ 1 ⊥ \mathbf{h}\in\mathbf{1}^{\perp} h ∈ 1 ⊥ . Let U ∈ R n × ( n − 1 ) U\in\mathbb{R}^{n\times(n-1)} U ∈ R n × ( n − 1 ) have orthonormal columns spanning 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ . We define the critical shift
τ c : = − λ min ( U ⊤ S U ) (4) \tau_c := -\lambda_{\min}(U^{\top} S U) \tag*{(4)} τ c := − λ m i n ( U ⊤ S U ) (4)
which is the negative of smallest eigenvalue of S S S restricted to zero-sum directions. Then E ^ ( ⋅ ) \hat{E}(\cdot) E ^ ( ⋅ ) is strictly convex on Δ n \Delta_n Δ n exactly when τ > τ c \tau>\tau_c τ > τ c , whereas S + τ I ⪰ 0 S+\tau I\succeq0 S + τ I ⪰ 0 requires τ > τ 0 \tau>\tau_0 τ > τ 0 , where τ 0 = − λ min ( S ) \tau_0=-\lambda_{\min}(S) τ 0 = − λ m i n ( S ) . Since U ⊤ S U U^{\top}SU U ⊤ S U is a compression of S S S , Cauchy interlacing [18 ] gives τ c ≤ τ 0 \tau_c\le\tau_0 τ c ≤ τ 0 (Lemma 1). For our affinity τ c = 17.09 \tau_c=17.09 τ c = 17.09 and τ 0 = 186.30 \tau_0=186.30 τ 0 = 186.30 ; Section C.3 traces this gap to a single outlier eigenvalue of S S S whose eigenvector is close to 1 \mathbf{1} 1 .
Invariance to a constant offset. Adding the same constant c c c to every affinity does not change the optimal mixture. On Δ n \Delta_n Δ n we have 1 ⊤ p = 1 \mathbf{1}^{\top}\mathbf{p}=1 1 ⊤ p = 1 , so replacing S S S by S + c 11 ⊤ S+c\mathbf{1}\mathbf{1}^{\top} S + c 1 1 ⊤ changes the pairwise term by 1 2 c ( 1 ⊤ p ) 2 = 1 2 c \frac{1}{2}c(\mathbf{1}^{\top}\mathbf{p})^2=\frac{1}{2}c 2 1 c ( 1 ⊤ p ) 2 = 2 1 c and the unary term β 1 ⊤ S p \beta\mathbf{1}^{\top}S\mathbf{p} β 1 ⊤ S p by β c n \beta c n β c n ; both are constants. The two shifts respond differently to such an offset. Because U ⊤ 1 = 0 U^{\top}\mathbf{1}=0 U ⊤ 1 = 0 , we have U ⊤ ( S + c 11 ⊤ ) U = U ⊤ S U U^{\top}(S+c\mathbf{1}\mathbf{1}^{\top})U=U^{\top}SU U ⊤ ( S + c 1 1 ⊤ ) U = U ⊤ S U , so τ c \tau_c τ c is unchanged, whereas τ 0 = − λ min ( S + c 11 ⊤ ) \tau_0=-\lambda_{\min}(S+c\mathbf{1}\mathbf{1}^{\top}) τ 0 = − λ m i n ( S + c 1 1 ⊤ ) increases monotonically towards τ c \tau_c τ c as c → ∞ c\to\infty c → ∞ . Hence τ c \tau_c τ c is intrinsic to the mixture problem, and τ 0 \tau_0 τ 0 depends on an offset the objective ignores (Section C.3).
Design Choices: Pairwise Potentials
Our objective function in Equation (3) depends critically on modeling pairwise interactions between tasks. To capture how task pairs correlate, it is essential to define a similarity metric that robustly encodes these relationships.
Pitfalls of Semantic Similarity Prior work [35 ] often relies on semantic similarity measures between tasks; however, these approaches are restrictive and agnostic to downstream model behavior. Figure 11a in Section F shows that cosine similarity between task vectors carries little information about task structure. We thereby move towards a more grounded similarity measure.
Pointwise Mutual Information Given two tasks T i , T j \mathcal{T}_i,\mathcal{T}_j T i , T j and corresponding datasets associated with it D T i = { x q T i , y q T i } q = 1 m 1 \mathcal{D}_{\mathcal{T}_i}=\{x_q^{\mathcal{T}_i},y_q^{\mathcal{T}_i}\}_{q=1}^{m_1} D T i = { x q T i , y q T i } q = 1 m 1 and D T j = { x r T j , y r T j } r = 1 m 2 \mathcal{D}_{\mathcal{T}_j}=\{x_r^{\mathcal{T}_j},y_r^{\mathcal{T}_j}\}_{r=1}^{m_2} D T j = { x r T j , y r T j } r = 1 m 2 respectively, we define the similarity score across two tasks
Figure 3. HeatMap of PMI Affinity Matrix across all 309 tasks as specified in Section K
T i T_i T i and T j T_j T j denoted as S P M I ( T i ; T j ) S_{\mathrm{PMI}}(T_i; T_j) S PMI ( T i ; T j )
S P M I ( T i ; T j ) : = 1 2 [ 1 m 2 ∑ r = 1 m 2 log P θ ∗ ( T i ) ( y r T j ∣ x r T j ) P θ ∗ ( T j ) ( y r T j ∣ x r T j ) + 1 m 1 ∑ q = 1 m 1 log P θ ∗ ( T j ) ( y q T i ∣ x q T i ) P θ ∗ ( T i ) ( y q T i ∣ x q T i ) ] (5) S_{\mathrm{PMI}}(T_i; T_j) := \frac{1}{2}\left[\frac{1}{m_2}\sum_{r=1}^{m_2}\log\frac{\mathbb{P}_{\theta^*(T_i)}\left(y_r^{T_j}\mid x_r^{T_j}\right)}{\mathbb{P}_{\theta^*(T_j)}\left(y_r^{T_j}\mid x_r^{T_j}\right)}+\frac{1}{m_1}\sum_{q=1}^{m_1}\log\frac{\mathbb{P}_{\theta^*(T_j)}\left(y_q^{T_i}\mid x_q^{T_i}\right)}{\mathbb{P}_{\theta^*(T_i)}\left(y_q^{T_i}\mid x_q^{T_i}\right)}\right] \tag*{(5)} S PMI ( T i ; T j ) := 2 1 m 2 1 r = 1 ∑ m 2 log P θ ∗ ( T j ) ( y r T j ∣ x r T j ) P θ ∗ ( T i ) ( y r T j ∣ x r T j ) + m 1 1 q = 1 ∑ m 1 log P θ ∗ ( T i ) ( y q T i ∣ x q T i ) P θ ∗ ( T j ) ( y q T i ∣ x q T i ) (5)
where θ ∗ ( T i ) : = θ 0 + τ ( T i ) \theta^*(T_i) := \theta_0+\tau(T_i) θ ∗ ( T i ) := θ 0 + τ ( T i ) , τ ( T i ) \tau(T_i) τ ( T i ) indicating the task vector for task T i T_i T i [32 ] and P θ ∗ ( T i ) \mathbb{P}_{\theta^*(T_i)} P θ ∗ ( T i ) indicates the next token probability scores under converged finetuned model parameter θ ∗ ( T i ) \theta^*(T_i) θ ∗ ( T i ) . How the scores are computed (models, held-out examples, cost) is described in Section D.1, and how to read their sign in Section C.1.
Task Discovery
From continuous mixtures to a set function over tasks. Given a current task mixture ξ k \xi_k ξ k composed of k k k tasks, our goal is to evaluate the marginal utility of introducing a new candidate task T k + 1 T_{k+1} T k + 1 to form an augmented mixture ξ k + 1 \xi_{k+1} ξ k + 1 . Considering V \mathcal{V} V as defined earlier (in Problem Setup : § 3 ) as the set of n n n tasks, for A ⊆ V \mathcal{A}\subseteq\mathcal{V} A ⊆ V with index set A ˉ ⊆ [ n ] \bar{\mathcal{A}}\subseteq[n] A ˉ ⊆ [ n ] , we define
f ( A ˉ ) : = max p ∈ Δ n , supp ( p ) ⊆ A ˉ E ( p ) , (6) f(\bar{\mathcal{A}}):=\max_{\substack{p\in\Delta_n,\\ \operatorname{supp}(p)\subseteq\bar{\mathcal{A}}}}\mathbb{E}(p), \tag*{(6)} f ( A ˉ ) := p ∈ Δ n , supp ( p ) ⊆ A ˉ max E ( p ) , (6)
with maximizer ζ ( A ˉ ) \zeta(\bar{\mathcal{A}}) ζ ( A ˉ ) , so that f ( A ˉ ) = E ( ζ ( A ˉ ) ) f(\bar{\mathcal{A}})=\mathbb{E}(\zeta(\bar{\mathcal{A}})) f ( A ˉ ) = E ( ζ ( A ˉ )) .
Incremental composition. Selecting at most k k k tasks therefore reduces to the problem max A ∈ I f ( A ˉ ) \max_{\mathcal{A}\in\mathcal{I}}f(\bar{\mathcal{A}}) max A ∈ I f ( A ˉ ) with I = { A ⊆ V : ∣ A ∣ ≤ k } \mathcal{I}=\{\mathcal{A}\subseteq\mathcal{V}:|\mathcal{A}|\leq k\} I = { A ⊆ V : ∣ A ∣ ≤ k } . This turns the continuous problem Equation (2) into a set function over tasks, and lets us build ξ k \xi_k ξ k one task at a time by adding the task that most increases f ( ⋅ ) f(\cdot) f ( ⋅ ) .
Task affinity. To measure how much adding a new task changes the overall mixture, we compare the learnt probability mixtures of ξ k \xi_k ξ k and ξ k + 1 \xi_{k+1} ξ k + 1 , given by p ∗ ( k ) p^*(k) p ∗ ( k ) and p ∗ ( k + 1 ) p^*(k+1) p ∗ ( k + 1 ) (with a slight abuse of notation, p ∗ ( k ) : = ζ ( ξ ˉ k ) p^*(k):=\zeta(\bar{\xi}_k) p ∗ ( k ) := ζ ( ξ ˉ k ) denotes the optimal mixture computed over k k k tasks). We compare p ∗ ( k ) p^*(k) p ∗ ( k ) with the restriction of p ∗ ( k + 1 ) p^*(k+1) p ∗ ( k + 1 ) to the first k k k tasks as TV ( p ∗ ( k ) , p ∗ ( k + 1 ) [ : k ] ) : = 1 2 ∑ i = 0 k − 1 ∣ p ∗ ( k ) [ i ] − p ∗ ( k + 1 ) [ i ] ∣ \operatorname{TV}(p^*(k),p^*(k+1)[:k]):=\frac{1}{2}\sum_{i=0}^{k-1}\left|p^*(k)_{[i]}-p^*(k+1)_{[i]}\right| TV ( p ∗ ( k ) , p ∗ ( k + 1 ) [ : k ]) := 2 1 ∑ i = 0 k − 1 p ∗ ( k ) [ i ] − p ∗ ( k + 1 ) [ i ] .
Remark 1. Intuitively, this metric tells us how much the existing mixture shifts when a new task joins it. Algorithm 1 Algorithm for TaskMixPGM
Figure 4a. Affinity as defined.
Figure 4b. Renormalised affinity T V ~ k \widetilde{\mathrm{TV}}_k TV k .
Figure 4c. Active tasks in p ∗ ( k ) p^*(k) p ∗ ( k ) .
Require: affinity S S S , ratio ρ > 0 \rho> 0 ρ > 0 , shift τ > τ c \tau> \tau_c τ > τ c , tolerance ϵ \epsilon ϵ
Ensure: p ∗ = arg min p ∈ Δ n 1 2 p T S ~ p − ρ 1 T S ~ p p^* = \arg\min_{p \in\Delta_n} \frac{1}{2}p^{\mathsf T}\widetilde{S}p - \rho\,\mathbf{1}^{\mathsf T}\widetilde{S}p p ∗ = arg min p ∈ Δ n 2 1 p T S p − ρ 1 T S p
S ~ ← S + τ I \widetilde{S} \leftarrow S + \tau I S ← S + τ I , L ← λ max ( S ~ ) L \leftarrow\lambda_{\max}(\widetilde{S}) L ← λ m a x ( S ) , p 0 = y 0 ← 1 n 1 p_0 = y_0 \leftarrow\frac{1}{n}\mathbf{1} p 0 = y 0 ← n 1 1 , t 0 ← 1 t_0 \leftarrow1 t 0 ← 1
for j = 0 , 1 , 2 , … j = 0, 1, 2, \ldots j = 0 , 1 , 2 , … do
p j + 1 ← Π Δ n ( y j − S ~ ( y j − ρ 1 ) / L ) p_{j+1} \leftarrow\Pi_{\Delta_n}\left(y_j - \widetilde{S}(y_j - \rho\mathbf{1})/L\right) p j + 1 ← Π Δ n ( y j − S ( y j − ρ 1 ) / L )
t j + 1 ← 1 2 ( 1 + 1 + 4 t j 2 ) t_{j+1} \leftarrow\frac{1}{2}\left(1 + \sqrt{1 + 4t_j^2}\right) t j + 1 ← 2 1 ( 1 + 1 + 4 t j 2 )
y j + 1 ← p j + 1 + t j − 1 t j + 1 ( p j + 1 − p j ) y_{j+1} \leftarrow p_{j+1} + \frac{t_j-1}{t_{j+1}}(p_{j+1} - p_j) y j + 1 ← p j + 1 + t j + 1 t j − 1 ( p j + 1 − p j )
if ∥ p j + 1 − p j ∥ 1 < ϵ \lVert p_{j+1} - p_j\rVert_1 < \epsilon ∥ p j + 1 − p j ∥ 1 < ϵ then return p j + 1 p_{j+1} p j + 1
end for
A small value means the weights of the first k k k tasks barely move, which typically happens when the new task is largely redundant with those already selected.
Renormalised affinity. Since ∑ i < k ( p ∗ ( k ) [ i ] − p ∗ ( k + 1 ) [ i ] ) = p ∗ ( k + 1 ) [ k ] \sum_{i<k}\left(p^*(k)_{[i]} - p^*(k+1)_{[i]}\right) = p^*(k+1)_{[k]} ∑ i < k ( p ∗ ( k ) [ i ] − p ∗ ( k + 1 ) [ i ] ) = p ∗ ( k + 1 ) [ k ] , the affinity above equals 1 2 p ∗ ( k + 1 ) [ k ] \frac{1}{2}p^*(k+1)_{[k]} 2 1 p ∗ ( k + 1 ) [ k ] whenever no existing task gains mass. In our runs this holds at every step where any existing weight changes, so the measure records the weight given to the new task rather than any reshuffling of the existing ones. We therefore also report T V ~ k : = T V ( p ∗ ( k ) , p ∗ ( k + 1 ) [ : k ] / ( 1 − p ∗ ( k + 1 ) [ k ] ) ) \widetilde{\mathrm{TV}}_k := \mathrm{TV}\left(p^*(k), p^*(k+1)_{[:k]}/(1-p^*(k+1)_{[k]})\right) TV k := TV ( p ∗ ( k ) , p ∗ ( k + 1 ) [ : k ] / ( 1 − p ∗ ( k + 1 ) [ k ] ) ) , which compares the two mixtures on the first k k k tasks after renormalisation. Both are reported along greedy and random insertion orders in Figure 4 and discussed in Section E.3.
Figure 4. Incremental composition. Solid: median over five random insertion orders (band: range). Dashed: greedy order. TV curves are a 15-step moving average. Markers: steps at which the unshifted (τ = 0 \tau= 0 τ = 0 ) mixture changes, each moving all mass to the new task. Grey dashed line in (c): all k k k tasks active.
Solver. Algorithm 1 is accelerated projected gradient (FISTA) on Equation (3) divided by λ \lambda λ , with the exact Euclidean projection onto Δ n \Delta_n Δ n . For τ > τ c \tau> \tau_c τ > τ c the problem is strictly convex on the simplex, so the algorithm returns the unique minimizer. With the settings used in all experiments (ρ = 0.02424 \rho= 0.02424 ρ = 0.02424 , τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 , ϵ = 10 − 14 \epsilon= 10^{-14} ϵ = 1 0 − 14 ) it converges in 38 iterations to a point that satisfies the full KKT conditions; details and verification are in Section C.5.
Instance-level sampling. Given the learnt mixture p ∗ ∈ Δ n p^* \in\Delta_n p ∗ ∈ Δ n , we allocate a budget of B \mathcal{B} B training instances across the n n n tasks by drawing B \mathcal{B} B i.i.d. task indices from p ∗ p^* p ∗ . The resulting counts k = ( k 1 , … , k n ) ∈ Z ≥ 0 n \mathbf{k} = (k_1,\ldots,k_n) \in\mathbb{Z}_{\geq0}^n k = ( k 1 , … , k n ) ∈ Z ≥ 0 n , with ∑ i = 1 n k i = B \sum_{i=1}^n k_i = \mathcal{B} ∑ i = 1 n k i = B , then follow k ∼ Mult ( B , p ∗ ) \mathbf{k} \sim\operatorname{Mult}(\mathcal{B},p^*) k ∼ Mult ( B , p ∗ ) :
P ( k ∣ B , p ∗ ) = B ! ∏ i = 1 n k i ! ∏ i = 1 n ( p [ i ] ∗ ) k i , E [ k i ] = B p [ i ] ∗ . \mathbb{P}(\mathbf{k}\mid\mathcal{B},p^*) = \frac{\mathcal{B}!}{\prod_{i=1}^{n} k_i!}\prod_{i=1}^{n}(p^*_{[i]})^{k_i}, \qquad\mathbb{E}[k_i] = \mathcal{B}p^*_{[i]}. P ( k ∣ B , p ∗ ) = ∏ i = 1 n k i ! B ! i = 1 ∏ n ( p [ i ] ∗ ) k i , E [ k i ] = B p [ i ] ∗ .
We then sample k i k_i k i instances uniformly from task T i \mathcal{T}_i T i , so tasks outside the support of p ∗ p^* p ∗ contribute nothing. In practice we average five such draws, round the result to integers that sum to B \mathcal{B} B , and cap each count at the size of its task (Section C.6).
Theoretical Results
The continuous view of Equation (3) yields mixture weights, but practical pipelines often require budgeted variants (e.g., selecting a subset of tasks and then optimizing proportions on that subset). To justify greedy construction in this discrete setting, we analyze the set function f ( ⋅ ) f(\cdot) f ( ⋅ ) of Eq. (6) , defined for nonempty supports. Any two points of Δ n \Delta_n Δ n always differ by a zero-sum vector, so the relevant curvature constants are the zero-sum restricted eigenvalues of Ψ p a i r \mathbf{\Psi}_{\mathrm{pair}} Ψ pair : for k ≥ 2 k \ge2 k ≥ 2 , m k m_k m k and M k M_k M k are the minimum and maximum of
h T Ψ p a i r h ∥ h ∥ 2 2 \frac{h^\mathsf{T}\mathbf{\Psi}_{\mathrm{pair}}h}{\lVert h\rVert_2^2} ∥ h ∥ 2 2 h T Ψ pair h
over nonzero h ∈ 1 ⊥ h \in\mathbf{1}^{\perp} h ∈ 1 ⊥ with at most k k k nonzero entries. For Ψ p a i r = λ ( S + τ I ) \mathbf{\Psi}_{\mathrm{pair}} = \lambda(S + \tau I) Ψ pair = λ ( S + τ I ) these satisfy m k ≥ λ ( τ − τ c ) m_k \ge\lambda(\tau-\tau_c) m k ≥ λ ( τ − τ c ) and M k ≤ λ ( τ + λ max ( U T S U ) ) M_k \le\lambda(\tau+ \lambda_{\max}(U^\mathsf{T}SU)) M k ≤ λ ( τ + λ m a x ( U T S U )) for every k k k , with τ c \tau_c τ c the critical shift of (4) . Full proofs appear in Appendix B.5.
Lemma 1 (Monotonicity). The set function f ( ⋅ ) f(\cdot) f ( ⋅ ) defined in Eq. (6) is monotone: for any nonempty P ⊆ Q ⊆ V \mathcal{P} \subseteq\mathcal{Q} \subseteq\mathcal{V} P ⊆ Q ⊆ V , f ( P ) ≤ f ( Q ) f(\mathcal{P}) \le f(\mathcal{Q}) f ( P ) ≤ f ( Q ) .
Proof sketch. If P ⊆ Q \mathcal{P} \subseteq\mathcal{Q} P ⊆ Q , then any mixture supported on P \mathcal{P} P is also feasible for Q \mathcal{Q} Q , so the feasible set only grows. Maximizing the same objective over a larger feasible set cannot reduce the optimum, hence f ( P ) ≤ f ( Q ) f(\mathcal{P}) \le f(\mathcal{Q}) f ( P ) ≤ f ( Q ) .
Lemma 2 (Restricted strong concavity and smoothness). Let Ψ p a i r \mathbf{\Psi}_{pair} Ψ p ai r be symmetric. For all p , q ∈ Δ n p, q \in\Delta_n p , q ∈ Δ n with ∣ supp ( p ) ∪ supp ( q ) ∣ ≤ k \lvert\operatorname{supp}(p) \cup\operatorname{supp}(q)\rvert\le k ∣ supp ( p ) ∪ supp ( q )∣ ≤ k , the energy E ( p ) = Ψ u n T p − 1 2 p T Ψ p a i r p \mathbb{E}(p) = \mathbf{\Psi}_{\mathrm{un}}^\mathsf{T}p - \frac{1}{2}p^\mathsf{T}\mathbf{\Psi}_{\mathrm{pair}}p E ( p ) = Ψ un T p − 2 1 p T Ψ pair p of (2) satisfies
− M k 2 ∥ p − q ∥ 2 2 ≤ E ( p ) − E ( q ) − ∇ E ( q ) T ( p − q ) -\frac{M_k}{2}\lVert p-q\rVert_2^2 \le\mathbb{E}(p)-\mathbb{E}(q)-\nabla\mathbb{E}(q)^\mathsf{T}(p-q) − 2 M k ∥ p − q ∥ 2 2 ≤ E ( p ) − E ( q ) − ∇ E ( q ) T ( p − q ) ≤ − m k 2 ∥ p − q ∥ 2 2 , \le-\frac{m_k}{2}\lVert p-q\rVert_2^2, ≤ − 2 m k ∥ p − q ∥ 2 2 , with finite constants, and m k > 0 m_k > 0 m k > 0 for every k k k whenever τ > τ c \tau> \tau_c τ > τ c .
Proof sketch. The Bregman remainder of the quadratic equals − 1 2 h T Ψ p a i r h -\frac{1}{2}h^\mathsf{T}\mathbf{\Psi}_{\mathrm{pair}}h − 2 1 h T Ψ pair h with h = p − q h=p-q h = p − q . This vector lies in 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ and has at most k k k nonzero entries. Apply the definition of m k m_k m k and M k M_k M k .
Theorem 1 (Weak submodularity). Let L , S ⊆ V \mathcal{L}, \mathcal{S} \subseteq\mathcal{V} L , S ⊆ V be disjoint with L ≠ ∅ \mathcal{L} \ne\varnothing L = ∅ , and suppose m ∣ L ∣ + ∣ S ∣ > 0 m_{\lvert\mathcal{L}\rvert+\lvert\mathcal{S}\rvert} > 0 m ∣ L ∣ + ∣ S ∣ > 0 (in particular, whenever τ > τ c \tau> \tau_c τ > τ c ). Then the submodularity ratio of f f f satisfies
γ L , S : = ∑ j ∈ S [ f ( L ∪ { j } ) − f ( L ) ] f ( L ∪ S ) − f ( L ) ≥ m ∣ L ∣ + ∣ S ∣ 2 M ∣ L ∣ + 1 \gamma_{\mathcal{L},\mathcal{S}} := \frac{\sum_{j\in\mathcal{S}}[f(\mathcal{L}\cup\{j\})-f(\mathcal{L})]}{f(\mathcal{L}\cup\mathcal{S})-f(\mathcal{L})} \ge\frac{m_{\lvert\mathcal{L}\rvert+\lvert\mathcal{S}\rvert}}{2M_{\lvert\mathcal{L}\rvert+1}} γ L , S := f ( L ∪ S ) − f ( L ) ∑ j ∈ S [ f ( L ∪ { j }) − f ( L )] ≥ 2 M ∣ L ∣ + 1 m ∣ L ∣ + ∣ S ∣ ≥ τ − τ c 2 ( τ + λ max ( U T S U ) ) > 0. \ge\frac{\tau-\tau_c}{2(\tau+\lambda_{\max}(U^\mathsf{T}SU))} > 0. ≥ 2 ( τ + λ m a x ( U T S U )) τ − τ c > 0.
The proof (Appendix B.6) adapts the restricted-strong-concavity argument of ProtoDash [17 Thm. 4.3] and [15 ] from the nonnegative orthant to the simplex. A new task can only enter by taking mass from the current support, along e j − ζ e_j-\zeta e j − ζ with step at most 1, which costs a factor 2. On a constrained face, the first-order condition is centered at the multiplier ν \nu ν , so the bound is naturally expressed in terms of ∇ j E − ν \nabla_j\mathbb{E}-\nu ∇ j E − ν . Combined with monotonicity, the greedy algorithm started from the best single task attains f ( A k ) − f ( A 1 ) ≥ ( 1 − e − γ k ) ( O P T k − 1 − f ( A 1 ) ) f(A_k)-f(A_1) \ge(1-e^{-\gamma_k})(\mathrm{OPT}_{k-1}-f(A_1)) f ( A k ) − f ( A 1 ) ≥ ( 1 − e − γ k ) ( OPT k − 1 − f ( A 1 )) with γ k = m 2 k − 1 / ( 2 M k + 1 ) \gamma_k = m_{2k-1}/(2M_{k+1}) γ k = m 2 k − 1 / ( 2 M k + 1 ) (Corollary 1, via DK11). Together, these properties support greedy budgeted task discovery with approximation guarantees. We instantiate the bound numerically (at τ = τ 0 \tau=\tau_0 τ = τ 0 ) and empirically verify weak submodularity in Appendix B.7 (Figure 6 ). Section E.3 studies how the mixture evolves when tasks are added one at a time.
(a) Diminishing returns.
(b) Greedy vs. random order.
(c) Empirical γ ^ A , S \widehat{\gamma}_{A,S} γ A , S .
(d) Curvature proxy m A / M A m_A/M_A m A / M A .
Figure 6. Weak submodularity of f f f . (a) Gain of five fixed tasks along greedy prefixes at τ 0 \tau_0 τ 0 (legend: greedy position of j j j ). (b) Gap f ( V ) − f ( A k ) f(\mathcal{V}) - f(A_k) f ( V ) − f ( A k ) for exact greedy (solid) and random orders (dashed, band over 5 random orders). (c) γ ^ A , S \widehat{\gamma}_{A,S} γ A , S (1) on the 180 random-set pairs per τ \tau τ (12 draws of A \mathcal{A} A per size, ∣ S ∣ ∈ { 2 , 5 , 10 } |S| \in\{2,5,10\} ∣ S ∣ ∈ { 2 , 5 , 10 } ). Pairs with f ( A ∪ S ‾ ) = f ( A ‾ ) f(\overline{\mathcal{A} \cup S}) = f(\overline{\mathcal{A}}) f ( A ∪ S ) = f ( A ) are omitted (0, 1 and 105 for τ 0 \tau_0 τ 0 , 50, 0). (d) m A / M A m_A/M_A m A / M A for ( S + τ I ) A (S + \tau I)_A ( S + τ I ) A along the τ 0 \tau_0 τ 0 greedy order, for τ ∈ { τ 0 , 50 , τ c , 0 } \tau\in\{\tau_0, 50, \tau_c, 0\} τ ∈ { τ 0 , 50 , τ c , 0 } , with τ c = 17.09 \tau_c = 17.09 τ c = 17.09 the critical shift of (4) . This principal-submatrix ratio is a conservative proxy for the zero-sum constants of Theorem 1; below zero (shaded) the proxy gives no guarantee.
Experimental Setup
To evaluate TaskMixPGM, we fine-tune recent 7B–9B models on mixtures drawn from 309 instruction-tuning tasks under varying training budgets. We evaluate on benchmarks spanning reasoning, knowledge, mathematics, and instruction following. We ask two questions: (1) does a single, benchmark-independent TaskMixPGM mixture outperform heuristic and existing selection methods (LESS and SMART)? and (2) what structure does the learned mixture exhibit, including task selection, pairwise effects, and stability as tasks are added?
Models. We evaluate TaskMixPGM on three decoder language models: Qwen-2-7B [51 ] , Llama-2-7B [40 ] and Qwen 3.5 9B Base [34 ] . Fine-tuning hyperparameters are reported in Section D.2.
Run variability. For each model and budget B \mathcal{B} B , we fine-tune three times with different random seeds and report the mean.
Instruction Corpora. We evaluate our framework on a diverse set of instruction tuning datasets spanning language understanding, reasoning, and knowledge. These include: Flan 2021 [25 , 8 ] (∼ \sim ∼ 17.5M examples), T0 [39 ] , Chain-of-Thought (CoT) [48 ] , Tulu V3 [28 , 44 ] , and GLUE/SuperGLUE [47 , 45 ] . Together these span 309 tasks (listed in Section K), providing a rich and heterogeneous testbed for data mixture selection.
Mixture hyperparameters. We compute a single mixture once from Qwen2-7B single-task models with ρ = 0.02424 \rho= 0.02424 ρ = 0.02424 (n ρ = 7.49 n\rho= 7.49 n ρ = 7.49 ) and τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 , and reuse it for all models and budgets; thus Llama-2-7B and Qwen3.5-9B results test transfer across families/sizes (Section D.1). This mixture has 206 active tasks and effective size e H ( p ∗ ) = 179.6 e^{H(p^*)} = 179.6 e H ( p ∗ ) = 179.6 (Table 4 ). We fix ρ \rho ρ a priori to target ∼ 2 / 3 \sim2/3 ∼ 2/3 coverage; Section C.4 gives the full ρ \rho ρ path, and Sections C.5 and C.6 describe mixture computation and sampling.
Table 4. Effect of the pairwise term along the ρ \rho ρ path (τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 ). TV is measured from p ∗ ( ρ ) p^*(\rho) p ∗ ( ρ ) to the pairwise-removed solution at the same ρ \rho ρ (no-pair) and to the degree-only allocation with the same support size (deg.).
Ablation: spectrum shift and offset effects. Motivated by our convexity-on-the-simplex analysis (§ 3.1 ), we ablate the spectrum shift τ \tau τ in S + τ I S + \tau I S + τ I (Figure 2 ). For PMI affinity, τ c = 17.09 \tau_c = 17.09 τ c = 17.09 whereas τ 0 = 186.30 \tau_0 = 186.30 τ 0 = 186.30 , an order-of-magnitude gap between simplex convexity and global PSD. As τ \tau τ decreases from τ 0 \tau_0 τ 0 , the learned mixture contracts smoothly (support 206 → 67 206 \to67 206 → 67 and effective size e H ( p ∗ ) e^{H(p^*)} e H ( p ∗ ) drops 179.6 → 44.6 179.6 \to44.6 179.6 → 44.6 by τ + \tau^+ τ + ), while at τ = 0 \tau= 0 τ = 0 projected gradient collapses to a single-task vertex, showing the shift is essential (Section C.3).
Figure 2. Effect of the spectrum shift τ \tau τ in S + τ I S+\tau I S + τ I on the optimal mixture (n = 309 n=309 n = 309 , ρ = 0.02424 \rho=0.02424 ρ = 0.02424 ). Shaded: τ ≤ τ c \tau\le\tau_c τ ≤ τ c , where the objective is not convex on Δ n \Delta_n Δ n . Dashed lines show the local minimum reached from p ∗ ( τ 0 ) \mathbf{p}^{*}(\tau_0) p ∗ ( τ 0 ) . At τ = 0 \tau=0 τ = 0 the solution is a single task. Per-collection mass is in Figure 9 ; discussion in Section C.3.
Baselines for Comparison. To evaluate the efficacy of our framework, we compare against several standard heuristic and SoTA data selection strategies.
We compare our methodology against the following baselines, where B \mathcal{B} B is the total instance budget, ∣ D i ∣ \lvert\mathcal{D}_i\rvert ∣ D i ∣ the size of task T i \mathcal{T}_i T i , and N = ∑ j = 1 n ∣ D j ∣ N = \sum_{j=1}^{n}\lvert\mathcal{D}_j\rvert N = ∑ j = 1 n ∣ D j ∣ the size of the pool (implementation details in Section D.3):
Uniform : equal weight per task, p [ i ] = 1 / n \boldsymbol{p}_{[i]} = 1/n p [ i ] = 1/ n , so each task contributes B / n \mathcal{B}/n B / n instances, sampled uniformly within the task.
EPM : weight proportional to task size, p [ i ] = ∣ D i ∣ / N \boldsymbol{p}_{[i]} = \lvert\mathcal{D}_i\rvert/N p [ i ] = ∣ D i ∣ / N , so task T i \mathcal{T}_i T i contributes B ∣ D i ∣ / N \mathcal{B}\lvert\mathcal{D}_i\rvert/N B ∣ D i ∣ / N instances, sampled uniformly within the task.
Random : B \mathcal{B} B instances drawn uniformly without replacement from the pooled set ⋃ D i \bigcup\mathcal{D}_i ⋃ D i ; in expectation each task contributes B ∣ D i ∣ / N \mathcal{B}\lvert\mathcal{D}_i\rvert/N B ∣ D i ∣ / N instances.
LESS [49 ] : an influence-function-based approach that selects training instances by gradient similarity to a target benchmark.
SMART [35 ] : uses submodular optimization to allocate the task budget and select diverse, non-redundant instances.
Evaluation Metrics. For the performance of our models, we evaluate on eleutherai/lm-evaluation-harness [37 ] on six Open LLM Leaderboard benchmarks: BBH , GPQA , IFEval , Math , MMLU-Pro and MUSR . The evaluation protocol is detailed in Section D.4.
Observations
Overall performance. Across the 36 model–budget–benchmark settings, TaskMixPGM scores highest in 32. On BBH, GPQA, Math, MMLU-Pro and MuSR it ranks first for every model and budget, and it beats the best of Random, Uniform and EPM in 35 of 36 settings. The margins are largest where reasoning matters most: on Llama-2-7B, BBH rises from 35.93 to 40.95 at 25K and from 35.65 to 41.59 at 50K over the strongest heuristic, and on Qwen3.5-9B-Base TaskMixPGM ranks first on all six benchmarks at both budgets. It also has the highest average score in all six model–budget blocks, ahead of the next-best method by 1.21 to 1.52 points on Qwen2-7B and Llama-2-7B and by 3.19 (25K) and 5.59 (50K) points on Qwen3.5-9B-Base. Results at a 100K budget on Llama-2-7B are in Section E.4.
Gains by capability. TaskMixPGM ranks first on every Reasoning, Knowledge and Math benchmark, for all three models and both budgets (30 of 30 settings). On Qwen2-7B and Llama-2-7B the leads are small, mostly 0.08 to 1.14 points (the largest is 2.85 on Llama-2-7B MuSR at 50K), but they are consistent: the runner-up changes from cell to cell among LESS, SMART, Uniform and EPM, while TaskMixPGM is never behind. On Qwen3.5-9B-Base the margins widen to 0.96–3.56 points on Reasoning, 2.35–4.53 on Knowledge (e.g. MMLU-Pro 56.84 vs. 52.83 for LESS at 50K) and 0.38–2.98 on Math.
Table 1. Instruct-tuning performance on Leaderboard benchmarks (25K and 50K samples). (a) Qwen2-7B; (b) Llama2-7B.
Table 2. Qwen3.5-9B.
Instruction following. IFEval is the only benchmark where TaskMixPGM does not always lead. On Qwen2-7B and Llama2-7B, SMART or Uniform is ahead by 0.14 to 3.24 points. On Qwen3.5-9B-Base the gap reverses: TaskMixPGM leads the strongest baseline by 9.96 points at 25K and 11.96 at 50K.
Comparison with LESS. LESS [49 ] selects data separately for each benchmark using gradient similarity, and trains one checkpoint per benchmark. TaskMixPGM trains a single checkpoint without access to any benchmark data, yet outperforms LESS in all 36 settings. It is also cheaper: computing the affinity matrix takes ≈ 16 \approx16 ≈ 16 GPU-hours on 8 H100s and is done once, after which Algorithm 1 returns a mixture for any budget in seconds. LESS needs ≈ 320 \approx320 ≈ 320 hours on 4 H100s to build its gradient datastore alone.
Effect of training budget. Doubling the budget from 25K to 50K improves TaskMixPGM in 16 of 18 model–benchmark pairs, with gains of up to 4.88 points on Qwen3.5-9B-Base (MuSR) and the only dips on Qwen2-7B GPQA and MMLU-Pro (−0.61 and −0.34). The baselines scale less reliably: SMART improves in only 9 of 18 pairs, losing up to 3.04 points on Llama-2-7B IFEval, and EPM improves in 10. A larger random or size-proportional sample can help one benchmark while hurting another, because extra data is not necessarily useful data. The selected mixture is also data-efficient: TaskMixPGM at 25K matches or beats the best heuristic at 50K in 15 of 18 pairs. We also discuss in detail contamination/overlap audits to Appendix § 16 .
Effect and Stability of Spectral Shifting
The two spectral-shift experiments are reported with the method (Figure 2 and Figure 4 ); we summarise their main takeaways here (details in Sections C.3 and E.3). Lowering the shift from τ 0 = 186.30 \tau_0 = 186.30 τ 0 = 186.30 toward τ c = 17.09 \tau_c = 17.09 τ c = 17.09 keeps the objective strictly convex on Δ n \Delta_n Δ n while shrinking the support from 206 to 67 tasks, with stable collection-level mass (T 0 T_0 T 0 : 0.62–0.65; Figure 9 ).
Figure 9. Share of mixture mass per source collection as the shift decreases. Down to τ c + \tau_c^+ τ c + the collection-level allocation is stable (T0 0.62–0.65), with FLAN2021 growing from 0.22 to 0.35. Without the shift all mass goes to one FLAN2021 task.
Conclusion
TaskMixPGM optimizes fine-tuning task mixtures by coupling utility with an MRF-based diversity term built from behavior-derived affinities. Empirically, a single benchmark-independent mixture computed once from Qwen2-7B transfers reliably across model families (Qwen2-7B, Qwen3.5-9B, Llama2-7B) and across mixture budgets, yielding consistent gains on multi-step reasoning and instruction-following benchmarks. These results support the view that behavior-derived task affinities provide a practical inductive bias for data selection beyond semantic heuristics, while remaining compatible with standard sampling pipelines. Beyond performance, our analysis highlights how the spectrum shift controls support size and stabilizes optimization, offering an interpretable knob for trading off diversity and representativeness. Overall, TaskMixPGM provides a simple, compute-efficient approach to constructing sparse mixtures that improve downstream generalization without requiring benchmark access during mixture design.
Limitations
Our experiments cover 309 instruction-tuning tasks and three base models in the 7B–9B range with two instance budgets (25K/50K), demonstrating strong transfer across families and budgets despite this constrained setting. Importantly, TaskMixPGM is modular: the same pipeline can be applied to larger task pools and model sizes as additional checkpoints and compute become available, and our analysis suggests the spectrum shift offers a simple mechanism to control sparsity and stability as scale increases. Affinity estimation relies on single-task checkpoints and held-out examples; however, this cost is incurred once and then amortized across mixture budgets, target models, and downstream deployments, making it practical when repeated fine-tuning runs are needed. Our evaluation centers on widely used leaderboard benchmarks to enable direct comparison with prior work; extending to additional axes (e.g., multilinguality, long-context, and safety) is a natural next step rather than a barrier to adoption. Finally, while hyperparameters such as ρ \rho ρ and the shift level can be tuned, the method performs well with a fixed setting across all reported experiments, indicating robustness and reducing the need for benchmark-specific calibration.
AI Use Statement
We used generative AI tools to assist with copy-editing and \LaTeX{} editing. All scientific claims, experimental results, and conclusions were produced and verified by the authors. We reviewed and edited all AI-assisted content and take full responsibility for this submission. Every item below can be verified from the released code, with all paths given relative to the repository root. The repository includes the scripts, configuration files, and intermediate results needed to reproduce the experiments and regenerate the tables and figures reported in the paper.
Checklist
For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. Yes (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. Yes (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. Yes
For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. Yes (b) Complete proofs of all theoretical results. Yes (c) Clear explanations of any assumptions. Yes
For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). Yes (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). Yes (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). Yes (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). Yes
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. Yes (b) The license information of the assets, if applicable. Yes (c) New assets either in the supplemental material or as a URL, if applicable. Not Applicable (d) Information about consent from data providers/curators. Not Applicable (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. Not Applicable
If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. Not Applicable (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. Not Applicable (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. Not Applicable
Organization of the Appendix
The appendix is organized in five parts.
Theory. Section B derives the KKT conditions and the interior closed form, and proves monotonicity, restricted strong concavity and weak submodularity of the support-restricted set function, with the greedy guarantee and a numerical and empirical check (Section B.7).
Mixture design. Section C explains how the mixture used in every experiment is obtained: why both potentials share one affinity matrix (Section C.1), the projection view of the objective (Section C.2), how much diagonal shift is needed and why τ c ≪ τ 0 \tau_c \ll\tau_0 τ c ≪ τ 0 (Section C.3), the trade-off ratio ρ \rho ρ as a coverage control and the operating point (Section C.4), the solver and its verification (Section C.5), and how the mixture is turned into a training set (Section C.6).
Experimental details. Section D describes how the affinity matrix was computed and what it costs (Section D.1), the final fine-tuning runs (Section D.2), the baselines (Section D.3) and the evaluation protocol (Section D.4).
Additional results and analysis. Section E analyses the structure of the learned mixture (Section E.1), the role of the pairwise term (Section E.2) and incremental composition (Section E.3), and reports additional fine-tuning results (Section E.4).
Further discussion. Section F compares notions of task similarity, Section G discusses benchmark contamination, Section H covers additional related work, § 18 the broader impact, Section J links to the code, and Section K lists all 309 tasks.
Theoretical Results and Proofs
Solution for Quadratic Minimization over the Simplex
We consider the problem of minimizing a quadratic energy function over the probability simplex Δ n \Delta_n Δ n :
min p ∈ Δ n E ( p ) : = − Ψ u n T p + 1 2 p T Ψ p a i r ( ⪰ 0 ) p (7) \min_{\mathbf{p}\in\Delta_n} E(\mathbf{p}) := -\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p} + \frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{(\succeq0)}\mathbf{p} \tag*{(7)} p ∈ Δ n min E ( p ) := − Ψ un T p + 2 1 p T Ψ pair ( ⪰ 0 ) p (7)
where Ψ u n ∈ R n \boldsymbol{\Psi}_{\mathrm{un}} \in\mathbb{R}^n Ψ un ∈ R n denotes a unary potential vector and Ψ p a i r ( ⪰ 0 ) ∈ R n × n \boldsymbol{\Psi}_{\mathrm{pair}}^{(\succeq0)} \in\mathbb{R}^{n\times n} Ψ pair ( ⪰ 0 ) ∈ R n × n is a symmetric positive semi-definite (PSD) matrix encoding pairwise interactions. For further analysis of the proof, we use the notation of Ψ p a i r ( ⪰ 0 ) \boldsymbol{\Psi}_{\mathrm{pair}}^{(\succeq0)} Ψ pair ( ⪰ 0 ) and Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair interchangeably.
Lagrangian and First-Order Conditions
To enforce the affine constraint p T 1 n = 1 \mathbf{p}^{\mathsf{T}}\mathbf{1}_n = 1 p T 1 n = 1 , and inequality constraints p ≥ 0 \mathbf{p} \ge0 p ≥ 0 , we consider the KKT conditions for optimality. Define the Lagrangian:
L ( p , ν , μ ) = − Ψ u n T p + 1 2 p T Ψ p a i r p + ν ( p T 1 n − 1 ) − μ T p (8) \mathcal{L}(\mathbf{p},\nu,\boldsymbol{\mu}) = -\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p} + \frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p} + \nu(\mathbf{p}^{\mathsf{T}}\mathbf{1}_n - 1) - \boldsymbol{\mu}^{\mathsf{T}}\mathbf{p} \tag*{(8)} L ( p , ν , μ ) = − Ψ un T p + 2 1 p T Ψ pair p + ν ( p T 1 n − 1 ) − μ T p (8)
with dual variables ν ∈ R \nu\in\mathbb{R} ν ∈ R (equality) and μ ∈ R + n \boldsymbol{\mu} \in\mathbb{R}^{n}_{+} μ ∈ R + n (inequality). The KKT optimality conditions are:
Stationarity.
∇ p L = − Ψ u n + Ψ p a i r p + ν 1 n − μ = 0. (9) \nabla_{\mathbf{p}}\mathcal{L} = -\boldsymbol{\Psi}_{\mathrm{un}} + \boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p} + \nu\mathbf{1}_n - \boldsymbol{\mu} = 0. \tag*{(9)} ∇ p L = − Ψ un + Ψ pair p + ν 1 n − μ = 0. (9)
∂ L ∂ p [ i ] = − Ψ u n [ i ] + ∑ j = 1 n Ψ p a i r [ i j ] p [ j ] + ν − μ [ i ] = 0 , ⇒ ν = Ψ u n [ i ] − ∑ j = 1 n Ψ p a i r [ i j ] p [ j ] + μ [ i ] . \begin{aligned}
\frac{\partial\mathcal{L}}{\partial p_{[i]}} = -\boldsymbol{\Psi}_{\mathrm{un}[i]} + \sum_{j=1}^{n}\boldsymbol{\Psi}_{\mathrm{pair}[ij]}p_{[j]} + \nu- \mu_{[i]} = 0, \\
&\Rightarrow\quad\nu= \boldsymbol{\Psi}_{\mathrm{un}[i]} - \sum_{j=1}^{n}\boldsymbol{\Psi}_{\mathrm{pair}[ij]}p_{[j]} + \mu_{[i]}.
\end{aligned} ∂ p [ i ] ∂ L = − Ψ un [ i ] + j = 1 ∑ n Ψ pair [ ij ] p [ j ] + ν − μ [ i ] = 0 , ⇒ ν = Ψ un [ i ] − j = 1 ∑ n Ψ pair [ ij ] p [ j ] + μ [ i ] .
Primal feasibility. 0 ≤ p [ i ] ≤ 1 0 \le p_{[i]} \le1 0 ≤ p [ i ] ≤ 1 for i ∈ [ n ] i \in[n] i ∈ [ n ] and ∑ i = 1 n p [ i ] = 1 \sum_{i=1}^{n}p_{[i]} = 1 ∑ i = 1 n p [ i ] = 1 .
Dual feasibility. ν ∈ R \nu\in\mathbb{R} ν ∈ R and μ [ i ] ≥ 0 \mu_{[i]} \ge0 μ [ i ] ≥ 0 .
Complementary slackness. μ [ i ] p [ i ] = 0 \mu_{[i]}p_{[i]} = 0 μ [ i ] p [ i ] = 0 for all i ∈ [ n ] i \in[n] i ∈ [ n ] .
Coordinate-wise cases.
(Active) If p [ i ] > 0 p_{[i]} > 0 p [ i ] > 0 , then μ [ i ] = 0 \mu_{[i]} = 0 μ [ i ] = 0 and ν = Ψ u n [ i ] − ∑ j = 1 n Ψ p a i r [ i j ] p [ j ] \nu= \boldsymbol{\Psi}_{\mathrm{un}[i]} - \sum_{j=1}^{n}\boldsymbol{\Psi}_{\mathrm{pair}[ij]}p_{[j]} ν = Ψ un [ i ] − ∑ j = 1 n Ψ pair [ ij ] p [ j ] .
(Inactive) If p [ i ] = 0 p_{[i]} = 0 p [ i ] = 0 , then μ [ i ] ≥ 0 \mu_{[i]} \ge0 μ [ i ] ≥ 0 , i.e. Ψ u n [ i ] − ∑ j Ψ p a i r [ i j ] p [ j ] ≤ ν \boldsymbol{\Psi}_{\mathrm{un}[i]} - \sum_{j}\boldsymbol{\Psi}_{\mathrm{pair}[ij]}p_{[j]} \le\nu Ψ un [ i ] − ∑ j Ψ pair [ ij ] p [ j ] ≤ ν .
Thus every task with positive weight has the same net utility Ψ u n [ i ] − ( Ψ p a i r p ) [ i ] = ν \boldsymbol{\Psi}_{\mathrm{un}[i]} - (\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p})_{[i]} = \nu Ψ un [ i ] − ( Ψ pair p ) [ i ] = ν , and every excluded task has net utility at most ν \nu ν . When Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair is positive definite on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ (i.e. τ > τ c \tau> \tau_c τ > τ c , Lemma 1), the problem is strictly convex on Δ n \Delta_n Δ n , so these conditions are also sufficient and identify the unique minimiser. If A = supp ( p ∗ ) \mathcal{A} = \operatorname{supp}(\mathbf{p}^{*}) A = supp ( p ∗ ) is known, the active block solves the linear system Ψ p a i r , A A p A = Ψ u n , A − ν 1 \boldsymbol{\Psi}_{\mathrm{pair},\mathcal{A}\mathcal{A}}\mathbf{p}_{\mathcal{A}} = \boldsymbol{\Psi}_{\mathrm{un},\mathcal{A}} - \nu\mathbf{1} Ψ pair , AA p A = Ψ un , A − ν 1 , 1 T p A = 1 \mathbf{1}^{\mathsf{T}}\mathbf{p}_{\mathcal{A}} = 1 1 T p A = 1 , i.e. (13) with all quantities restricted to A \mathcal{A} A .
Solution under Interior Assumption
We first consider the case where the solution lies in the relative interior of the simplex; that is, p ∗ > 0 \mathbf{p}^{*} > 0 p ∗ > 0 and hence μ = 0 \boldsymbol{\mu} = 0 μ = 0 . Substituting into (9), we obtain:
Ψ p a i r p = Ψ u n − ν 1 n (10) \boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p} = \boldsymbol{\Psi}_{\mathrm{un}} - \nu\mathbf{1}_n \tag*{(10)} Ψ pair p = Ψ un − ν 1 n (10)
Assuming Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair is invertible (positive definiteness is not needed for this step), we may solve:
p = Ψ p a i r − 1 Ψ u n − ν Ψ p a i r − 1 1 n (11) \mathbf{p} = \boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\boldsymbol{\Psi}_{\mathrm{un}} - \nu\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\mathbf{1}_n \tag*{(11)} p = Ψ pair − 1 Ψ un − ν Ψ pair − 1 1 n (11)
Imposing the constraint p T 1 n = 1 \mathbf{p}^{\mathsf{T}}\mathbf{1}_n = 1 p T 1 n = 1 , we find:
1 n T p = 1 n T Ψ p a i r − 1 Ψ u n − ν 1 n T Ψ p a i r − 1 1 n = 1 (12) \mathbf{1}_n^{\mathsf{T}}\mathbf{p} = \mathbf{1}_n^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\boldsymbol{\Psi}_{\mathrm{un}} - \nu\mathbf{1}_n^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\mathbf{1}_n = 1 \tag*{(12)} 1 n T p = 1 n T Ψ pair − 1 Ψ un − ν 1 n T Ψ pair − 1 1 n = 1 (12)
Letting
a : = 1 n T Ψ p a i r − 1 Ψ u n , b : = 1 n T Ψ p a i r − 1 1 n , a := \mathbf{1}_n^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\boldsymbol{\Psi}_{\mathrm{un}}, \qquad b := \mathbf{1}_n^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\mathbf{1}_n, a := 1 n T Ψ pair − 1 Ψ un , b := 1 n T Ψ pair − 1 1 n ,
we obtain ν = a − 1 b \nu= \frac{a-1}{b} ν = b a − 1 .
Substituting back into the expression for p \mathbf{p} p , we conclude:
p ∗ = Ψ p a i r − 1 Ψ u n − 1 n T Ψ p a i r − 1 Ψ u n − 1 1 n T Ψ p a i r − 1 1 n ⋅ Ψ p a i r − 1 1 n (13) \mathbf{p}^{*}=\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\boldsymbol{\Psi}_{\mathrm{un}}-\frac{\mathbf{1}_{n}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\boldsymbol{\Psi}_{\mathrm{un}}-1}{\mathbf{1}_{n}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\mathbf{1}_{n}}\cdot\boldsymbol{\Psi}_{\mathrm{pair}}^{-1}\mathbf{1}_{n} \tag*{(13)} p ∗ = Ψ pair − 1 Ψ un − 1 n T Ψ pair − 1 1 n 1 n T Ψ pair − 1 Ψ un − 1 ⋅ Ψ pair − 1 1 n (13)
Discussion
The closed-form expression (13) satisfies the affine constraint by construction, and requires Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair to be invertible. If p ∗ ≥ 0 \mathbf{p}^{*}\geq0 p ∗ ≥ 0 componentwise and Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair is positive definite on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ (τ > τ c \tau>\tau_{c} τ > τ c ), it satisfies all KKT conditions with μ = 0 \boldsymbol{\mu}=\mathbf{0} μ = 0 and is therefore the unique global minimizer. Invertibility alone is not enough: if Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair is indefinite on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , the stationary point can be a saddle. Otherwise, if any coordinate is negative, the interior assumption fails, and active-set refinement or projection onto the simplex is required. In practice, one may use projection-based algorithms (e.g., conditional gradient, projected gradient descent) or iteratively restrict to the support set of nonnegative entries and resolve (13) over that face of the simplex.
Monotonicity and Submodular Properties of Energy Potential
Setting and notation. Throughout this section E ( p ) = Ψ u n T p − 1 2 p T Ψ p a i r p \mathbb{E}(\mathbf{p})=\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p}-\frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p} E ( p ) = Ψ un T p − 2 1 p T Ψ pair p with Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair symmetric; in the algorithm Ψ p a i r = λ S ~ e = λ ( S + τ I ) \boldsymbol{\Psi}_{\mathrm{pair}}=\lambda\widetilde{S}_{e}=\lambda(S+\tau I) Ψ pair = λ S e = λ ( S + τ I ) and Ψ u n = β S ~ e 1 \boldsymbol{\Psi}_{\mathrm{un}}=\beta\widetilde{S}_{e}\mathbf{1} Ψ un = β S e 1 . For a nonempty A ⊆ V A\subseteq\mathcal{V} A ⊆ V let F ( A ) : = { p ∈ Δ n : supp ( p ) ⊆ A } F(A):=\{\mathbf{p}\in\Delta_{n}:\operatorname{supp}(\mathbf{p})\subseteq A\} F ( A ) := { p ∈ Δ n : supp ( p ) ⊆ A } (a face of the simplex), f ( A ) : = max p ∈ F ( A ) E ( p ) f(A):=\max_{\mathbf{p}\in F(A)}\mathbb{E}(\mathbf{p}) f ( A ) := max p ∈ F ( A ) E ( p ) , and let ζ ( A ) \zeta^{(A)} ζ ( A ) denote a maximiser. f ( ∅ ) f(\varnothing) f ( ∅ ) is undefined because F ( ∅ ) = ∅ F(\varnothing)=\varnothing F ( ∅ ) = ∅ ; this is handled in Corollary 1. Since any two points of Δ n \Delta_{n} Δ n differ by a zero-sum vector, curvature only matters along 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ . For k ≥ 2 k\geq2 k ≥ 2 we therefore define the zero-sum restricted eigenvalues
m k : = min h ∈ 1 ⊥ ∖ { 0 } ∥ h ∥ 0 ≤ k h T Ψ p a i r h ∥ h ∥ 2 2 , M k : = max h ∈ 1 ⊥ ∖ { 0 } ∥ h ∥ 0 ≤ k h T Ψ p a i r h ∥ h ∥ 2 2 . (14) m_{k}:=\min_{\substack{\mathbf{h}\in\mathbf{1}^{\perp}\setminus\{0\}\\ \|\mathbf{h}\|_{0}\leq k}}\frac{\mathbf{h}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{h}}{\|\mathbf{h}\|_{2}^{2}},\qquad M_{k}:=\max_{\substack{\mathbf{h}\in\mathbf{1}^{\perp}\setminus\{0\}\\ \|\mathbf{h}\|_{0}\leq k}}\frac{\mathbf{h}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{h}}{\|\mathbf{h}\|_{2}^{2}}. \tag*{(14)} m k := h ∈ 1 ⊥ ∖ { 0 } ∥ h ∥ 0 ≤ k min ∥ h ∥ 2 2 h T Ψ pair h , M k := h ∈ 1 ⊥ ∖ { 0 } ∥ h ∥ 0 ≤ k max ∥ h ∥ 2 2 h T Ψ pair h . (14)
m k m_{k} m k is non-increasing and M k M_{k} M k non-decreasing in k k k . With B B B an orthonormal basis of 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ and τ c = − λ min ( B T S B ) \tau_{c}=-\lambda_{\min}(B^{\mathsf{T}}SB) τ c = − λ m i n ( B T S B ) as in Lemma 1,
m k ≥ λ ( τ − τ c ) , M k ≤ λ ( τ + λ max ( B T S B ) ) for all k , (15) m_{k}\geq\lambda(\tau-\tau_{c}),\qquad M_{k}\leq\lambda\left(\tau+\lambda_{\max}(B^{\mathsf{T}}SB)\right)\qquad\text{for all }k, \tag*{(15)} m k ≥ λ ( τ − τ c ) , M k ≤ λ ( τ + λ m a x ( B T S B ) ) for all k , (15)
because restricting the Rayleigh quotient to sparse vectors can only raise its minimum and lower its maximum. In particular m k > 0 m_{k}>0 m k > 0 for every k k k whenever τ > τ c \tau>\tau_{c} τ > τ c , which is a much weaker requirement than S ~ ≻ 0 \widetilde{S}\succ0 S ≻ 0 (τ > τ 0 \tau>\tau_{0} τ > τ 0 ).
Lemma 1 (Monotonicity). The set function f ( ⋅ ) f(\cdot) f ( ⋅ ) defined in Eq. (6) is monotone: for any nonempty P ⊆ Q ⊆ V P\subseteq Q\subseteq\mathcal{V} P ⊆ Q ⊆ V , f ( P ) ≤ f ( Q ) f(P)\leq f(Q) f ( P ) ≤ f ( Q ) .
Proof. Let ∅ ≠ P ⊆ Q \varnothing\neq P\subseteq Q ∅ = P ⊆ Q . Every p \mathbf{p} p with supp ( p ) ⊆ P \operatorname{supp}(\mathbf{p})\subseteq P supp ( p ) ⊆ P also has supp ( p ) ⊆ Q \operatorname{supp}(\mathbf{p})\subseteq Q supp ( p ) ⊆ Q , so F ( P ) ⊆ F ( Q ) F(P)\subseteq F(Q) F ( P ) ⊆ F ( Q ) . Both faces are nonempty and compact and E \mathbb{E} E is continuous, so both maxima are attained, and maximising the same function over a larger set cannot decrease the maximum: f ( Q ) = max F ( Q ) E ≥ E ( ζ ( P ) ) = f ( P ) f(Q)=\max_{F(Q)}\mathbb{E}\geq\mathbb{E}(\zeta^{(P)})=f(P) f ( Q ) = max F ( Q ) E ≥ E ( ζ ( P ) ) = f ( P ) . No concavity or definiteness assumption is needed.
Lemma 2 (Restricted strong concavity and smoothness). Let Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair be symmetric. For all p , q ∈ Δ n \mathbf{p},\mathbf{q}\in\Delta_{n} p , q ∈ Δ n with ∣ supp ( p ) ∪ supp ( q ) ∣ ≤ k |\operatorname{supp}(\mathbf{p})\cup\operatorname{supp}(\mathbf{q})|\leq k ∣ supp ( p ) ∪ supp ( q ) ∣ ≤ k , the energy E ( p ) = Ψ u n T p − 1 2 p T Ψ p a i r p \mathbb{E}(\mathbf{p})=\boldsymbol{\Psi}_{\mathrm{un}}^{\mathsf{T}}\mathbf{p}-\frac{1}{2}\mathbf{p}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{p} E ( p ) = Ψ un T p − 2 1 p T Ψ pair p of (2) satisfies
− M k 2 ∥ p − q ∥ 2 2 ≤ E ( p ) − E ( q ) − ∇ E ( q ) T ( p − q ) -\frac{M_{k}}{2}\|\mathbf{p}-\mathbf{q}\|_{2}^{2}\leq\mathbb{E}(\mathbf{p})-\mathbb{E}(\mathbf{q})-\nabla\mathbb{E}(\mathbf{q})^{\mathsf{T}}(\mathbf{p}-\mathbf{q}) − 2 M k ∥ p − q ∥ 2 2 ≤ E ( p ) − E ( q ) − ∇ E ( q ) T ( p − q ) ≤ − m k 2 ∥ p − q ∥ 2 2 , \leq-\frac{m_{k}}{2}\|\mathbf{p}-\mathbf{q}\|_{2}^{2}, ≤ − 2 m k ∥ p − q ∥ 2 2 , with finite constants, and m k > 0 m_{k}>0 m k > 0 for every k k k whenever τ > τ c \tau>\tau_{c} τ > τ c .
Proof. Let p , q ∈ Δ n \mathbf{p},\mathbf{q}\in\Delta_{n} p , q ∈ Δ n with ∣ supp ( p ) ∪ supp ( q ) ∣ ≤ k |\operatorname{supp}(\mathbf{p})\cup\operatorname{supp}(\mathbf{q})|\leq k ∣ supp ( p ) ∪ supp ( q ) ∣ ≤ k and set h = p − q \mathbf{h}=\mathbf{p}-\mathbf{q} h = p − q . Then 1 T h = 1 − 1 = 0 \mathbf{1}^{\mathsf{T}}\mathbf{h}=1-1=0 1 T h = 1 − 1 = 0 and ∥ h ∥ 0 ≤ k \|\mathbf{h}\|_{0}\leq k ∥ h ∥ 0 ≤ k . Since ∇ E ( q ) = Ψ u n − Ψ p a i r q \nabla\mathbb{E}(\mathbf{q})=\boldsymbol{\Psi}_{\mathrm{un}}-\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{q} ∇ E ( q ) = Ψ un − Ψ pair q , expanding the quadratic gives the exact identity
E ( p ) − E ( q ) − ∇ E ( q ) T h = − 1 2 h T Ψ p a i r h . \mathbb{E}(\mathbf{p})-\mathbb{E}(\mathbf{q})-\nabla\mathbb{E}(\mathbf{q})^{\mathsf{T}}\mathbf{h}=-\frac{1}{2}\mathbf{h}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{h}. E ( p ) − E ( q ) − ∇ E ( q ) T h = − 2 1 h T Ψ pair h . By the definition (14) , m k ∥ h ∥ 2 2 ≤ h T Ψ p a i r h ≤ M k ∥ h ∥ 2 2 m_{k}\|\mathbf{h}\|_{2}^{2}\leq\mathbf{h}^{\mathsf{T}}\boldsymbol{\Psi}_{\mathrm{pair}}\mathbf{h}\leq M_{k}\|\mathbf{h}\|_{2}^{2} m k ∥ h ∥ 2 2 ≤ h T Ψ pair h ≤ M k ∥ h ∥ 2 2 , which is the claim. Both constants are finite for any symmetric Ψ p a i r \boldsymbol{\Psi}_{\mathrm{pair}} Ψ pair (∣ m k ∣ , ∣ M k ∣ ≤ ∥ Ψ p a i r ∥ 2 |m_{k}|,|M_{k}|\leq\|\boldsymbol{\Psi}_{\mathrm{pair}}\|_{2} ∣ m k ∣ , ∣ M k ∣ ≤ ∥ Ψ pair ∥ 2 ), and m k > 0 m_{k}>0 m k > 0 whenever τ > τ c \tau>\tau_{c} τ > τ c by (15) .
Remark 2 (Sign convention). Because E E E is concave, the Bregman remainder is non-positive ; restricted strong concavity and smoothness of E E E are restricted strong convexity and smoothness of − E -E − E , which is the form used by [15 ] and [17 ] .
Weak Submodularity of Set function f f f
We follow the template of [17 Thm. 4.3] (ProtoDash), itself an instance of [15 ] : bound the joint gain f ( L ∪ S ) − f ( L ) f(\mathcal{L}\cup S)-f(\mathcal{L}) f ( L ∪ S ) − f ( L ) from above by restricted strong concavity, and each single gain f ( L ∪ { j } ) − f ( L ) f(\mathcal{L}\cup\{j\})-f(\mathcal{L}) f ( L ∪ { j }) − f ( L ) from below by restricted smoothness, both in terms of the gradient at ζ ( L ) \zeta^{(\mathcal{L})} ζ ( L ) . ProtoDash optimises over the nonnegative orthant, where a new element can be added with any weight α ≥ 0 \alpha\ge0 α ≥ 0 while the others stay fixed, and where optimality of ζ ( L ) \zeta^{(\mathcal{L})} ζ ( L ) makes the gradient vanish on its support. On the simplex neither holds, and the argument needs three changes: (i) adding j j j must move mass away from L \mathcal{L} L , i.e. along e j − ζ ( L ) e_j-\zeta^{(\mathcal{L})} e j − ζ ( L ) with step α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] ; (ii) at ζ ( L ) \zeta^{(\mathcal{L})} ζ ( L ) the gradient equals the Lagrange multiplier ν \nu ν (not 0) on the support, so the relevant quantity is the gap g j : = ∇ j E ( ζ ( L ) ) − ν g_j:=\nabla_jE(\zeta^{(\mathcal{L})})-\nu g j := ∇ j E ( ζ ( L ) ) − ν (the Frank–Wolfe gap of direction j j j ); (iii) curvature is only needed along 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , which yields (14) instead of ordinary sparse eigenvalues. The price of the step cap α ≤ 1 \alpha\le1 α ≤ 1 is a factor 2 in the ratio.
Theorem 1 (Weak submodularity). Let L , S ⊆ V \mathcal{L},S\subseteq V L , S ⊆ V be disjoint with L ≠ ∅ \mathcal{L}\ne\varnothing L = ∅ , and suppose m ∣ L ∣ + ∣ S ∣ > 0 m_{|\mathcal{L}|+|S|}>0 m ∣ L ∣ + ∣ S ∣ > 0 (in particular, whenever τ > τ c \tau>\tau_c τ > τ c ). Then the submodularity ratio of f f f satisfies
γ L , S : = ∑ j ∈ S [ f ( L ∪ { j } ) − f ( L ) ] f ( L ∪ S ) − f ( L ) ≥ m ∣ L ∣ + ∣ S ∣ 2 M ∣ L ∣ + 1 \gamma_{\mathcal{L},S}:=\frac{\sum_{j\in S}\left[f(\mathcal{L}\cup\{j\})-f(\mathcal{L})\right]}{f(\mathcal{L}\cup S)-f(\mathcal{L})}\ge\frac{m_{|\mathcal{L}|+|S|}}{2M_{|\mathcal{L}|+1}} γ L , S := f ( L ∪ S ) − f ( L ) ∑ j ∈ S [ f ( L ∪ { j }) − f ( L ) ] ≥ 2 M ∣ L ∣ + 1 m ∣ L ∣ + ∣ S ∣ ≥ τ − τ c 2 ( τ + λ max ( U T S U ) ) > 0. \ge\frac{\tau-\tau_c}{2(\tau+\lambda_{\max}(U^{\mathsf{T}}SU))}>0. ≥ 2 ( τ + λ m a x ( U T S U )) τ − τ c > 0.
Proof. Write ζ : = ζ ( L ) \zeta:=\zeta^{(\mathcal{L})} ζ := ζ ( L ) , ∇ : = ∇ E ( ζ ) \nabla:=\nabla E(\zeta) ∇ := ∇ E ( ζ ) , and ν : = ∇ T ζ \nu:=\nabla^{\mathsf{T}}\zeta ν := ∇ T ζ . Set m : = m ∣ L ∣ + ∣ S ∣ > 0 m:=m_{|\mathcal{L}|+|S|}>0 m := m ∣ L ∣ + ∣ S ∣ > 0 and M : = M ∣ L ∣ + 1 M:=M_{|\mathcal{L}|+1} M := M ∣ L ∣ + 1 . Note M ≥ m 2 ≥ m > 0 M\ge m_2\ge m>0 M ≥ m 2 ≥ m > 0 , since ∣ L ∣ + 1 ≥ 2 |\mathcal{L}|+1\ge2 ∣ L ∣ + 1 ≥ 2 .
Step 1 (optimality of ζ \zeta ζ on the face F ( L ) \mathcal{F}(\mathcal{L}) F ( L ) ). ζ \zeta ζ maximises a differentiable function over the face, which is a polytope, so the KKT conditions hold without further qualification: there are ν ′ ∈ R \nu'\in\mathbb{R} ν ′ ∈ R and μ ≥ 0 \mu\ge0 μ ≥ 0 with ∇ [ i ] = ν ′ − μ [ i ] \nabla_{[i]}=\nu'-\mu_{[i]} ∇ [ i ] = ν ′ − μ [ i ] and μ [ i ] ζ [ i ] = 0 \mu_{[i]}\zeta_{[i]}=0 μ [ i ] ζ [ i ] = 0 for i ∈ L i\in\mathcal{L} i ∈ L . Multiplying by ζ \zeta ζ and summing gives ν ′ = ν \nu'=\nu ν ′ = ν . Hence
∇ [ i ] = ν if ζ [ i ] > 0 , ∇ [ i ] ≤ ν if i ∈ L , ζ [ i ] = 0. (16) \nabla_{[i]}=\nu\ \text{ if }\ \zeta_{[i]}>0,\qquad\nabla_{[i]}\le\nu\ \text{ if }i\in\mathcal{L},\ \zeta_{[i]}=0. \tag*{(16)} ∇ [ i ] = ν if ζ [ i ] > 0 , ∇ [ i ] ≤ ν if i ∈ L , ζ [ i ] = 0. (16)
For j ∈ S j\in S j ∈ S define the gap g j : = ∇ [ j ] − ν g_j:=\nabla_{[j]}-\nu g j := ∇ [ j ] − ν and g j + : = max { g j , 0 } g_j^+:=\max\{g_j,0\} g j + := max { g j , 0 } , and write g S + : = ( g j + ) j ∈ S g_S^+:=(g_j^+)_{j\in S} g S + := ( g j + ) j ∈ S .
Step 2 (upper bound on the joint gain). Let p ∈ F ( L ∪ S ) p\in\mathcal{F}(\mathcal{L}\cup S) p ∈ F ( L ∪ S ) and h : = p − ζ h:=p-\zeta h := p − ζ . Then 1 T h = 0 \mathbf{1}^{\mathsf{T}}h=0 1 T h = 0 and supp ( h ) ⊆ L ∪ S \operatorname{supp}(h)\subseteq\mathcal{L}\cup S supp ( h ) ⊆ L ∪ S . Using 1 T h = 0 \mathbf{1}^{\mathsf{T}}h=0 1 T h = 0 ,
∇ T h = ∑ i ( ∇ [ i ] − ν ) h [ i ] = ∑ i ∈ L ( ∇ [ i ] − ν ) h [ i ] + ∑ j ∈ S g j p [ j ] ≤ ∑ j ∈ S g j + p [ j ] . \nabla^{\mathsf{T}}h=\sum_i(\nabla_{[i]}-\nu)h_{[i]}=\sum_{i\in\mathcal{L}}(\nabla_{[i]}-\nu)h_{[i]}+\sum_{j\in S}g_jp_{[j]}\le\sum_{j\in S}g_j^+p_{[j]}. ∇ T h = i ∑ ( ∇ [ i ] − ν ) h [ i ] = i ∈ L ∑ ( ∇ [ i ] − ν ) h [ i ] + j ∈ S ∑ g j p [ j ] ≤ j ∈ S ∑ g j + p [ j ] .
The first sum is non-positive by (16) : its terms vanish where ζ [ i ] > 0 \zeta_{[i]}>0 ζ [ i ] > 0 , and where ζ [ i ] = 0 \zeta_{[i]}=0 ζ [ i ] = 0 we have h [ i ] = p [ i ] ≥ 0 h_{[i]}=p_{[i]}\ge0 h [ i ] = p [ i ] ≥ 0 and ∇ [ i ] − ν < 0 \nabla_{[i]}-\nu<0 ∇ [ i ] − ν < 0 . For j ∈ S j\in S j ∈ S we used ζ [ j ] = 0 \zeta_{[j]}=0 ζ [ j ] = 0 , so h [ j ] = p [ j ] ≥ 0 h_{[j]}=p_{[j]}\ge0 h [ j ] = p [ j ] ≥ 0 . The last sum is at most ∥ g S + ∥ 2 ∥ h ∥ 2 \lVert g_S^+\rVert_2\lVert h\rVert_2 ∥ g S + ∥ 2 ∥ h ∥ 2 (Cauchy–Schwarz) and also at most g max : = max j ∈ S g j + g_{\max}:=\max_{j\in S}g_j^+ g m a x := max j ∈ S g j + , since ∑ j ∈ S p [ j ] ≤ 1 \sum_{j\in S}p_{[j]}\le1 ∑ j ∈ S p [ j ] ≤ 1 . Applying Lemma 2 with k = ∣ L ∣ + ∣ S ∣ k=|\mathcal{L}|+|S| k = ∣ L ∣ + ∣ S ∣ :
E ( p ) − E ( ζ ) ≤ ∇ T h − m 2 ∥ h ∥ 2 2 ≤ ∥ g S + ∥ 2 ∥ h ∥ 2 − m 2 ∥ h ∥ 2 2 ≤ ∥ g S + ∥ 2 2 2 m , \mathbb{E}(p)-\mathbb{E}(\zeta)\le\nabla^{\mathsf{T}}h-\frac{m}{2}\lVert h\rVert_2^2\le\lVert g_S^+\rVert_2\lVert h\rVert_2-\frac{m}{2}\lVert h\rVert_2^2\le\frac{\lVert g_S^+\rVert_2^2}{2m}, E ( p ) − E ( ζ ) ≤ ∇ T h − 2 m ∥ h ∥ 2 2 ≤ ∥ g S + ∥ 2 ∥ h ∥ 2 − 2 m ∥ h ∥ 2 2 ≤ 2 m ∥ g S + ∥ 2 2 ,
and also E ( p ) − E ( ζ ) ≤ ∇ T h ≤ g max \mathbb{E}(p)-\mathbb{E}(\zeta)\le\nabla^{\mathsf{T}}h\le g_{\max} E ( p ) − E ( ζ ) ≤ ∇ T h ≤ g m a x . Maximising over p p p ,
f ( L ∪ S ) − f ( L ) ≤ min { ∥ g S + ∥ 2 2 2 m , g max } . (17) f(\mathcal{L}\cup S)-f(\mathcal{L})\le\min\left\{\frac{\lVert g_S^+\rVert_2^2}{2m},\,g_{\max}\right\}. \tag*{(17)} f ( L ∪ S ) − f ( L ) ≤ min { 2 m ∥ g S + ∥ 2 2 , g m a x } . (17)
Step 3 (lower bound on each single gain). Fix j ∈ S j\in S j ∈ S with g j > 0 g_j>0 g j > 0 and let d j : = e j − ζ d_j:=e_j-\zeta d j := e j − ζ . For α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] , ζ + α d j ∈ F ( L ∪ { j } ) \zeta+\alpha d_j\in\mathcal{F}(\mathcal{L}\cup\{j\}) ζ + α d j ∈ F ( L ∪ { j }) . Since E E E is quadratic,
E ( ζ + α d j ) − E ( ζ ) = α ∇ T d j − α 2 2 d j T Ψ p a i r d j ≥ α g j − α 2 2 M D j , \mathbb{E}(\zeta+\alpha d_j)-\mathbb{E}(\zeta)=\alpha\nabla^{\mathsf{T}}d_j-\frac{\alpha^2}{2}d_j^{\mathsf{T}}\Psi_{\mathrm{pair}}d_j\ge\alpha g_j-\frac{\alpha^2}{2}MD_j, E ( ζ + α d j ) − E ( ζ ) = α ∇ T d j − 2 α 2 d j T Ψ pair d j ≥ α g j − 2 α 2 M D j ,
where we used ∇ T d j = ∇ [ j ] − ν = g j \nabla^{\mathsf{T}}d_j=\nabla_{[j]}-\nu=g_j ∇ T d j = ∇ [ j ] − ν = g j , and d j ∈ 1 ⊥ d_j\in\mathbf{1}^{\perp} d j ∈ 1 ⊥ with ∥ d j ∥ 0 ≤ ∣ L ∣ + 1 \lVert d_j\rVert_0\le|\mathcal{L}|+1 ∥ d j ∥ 0 ≤ ∣ L ∣ + 1 , so d j T Ψ p a i r d j ≤ M D j d_j^{\mathsf{T}}\Psi_{\mathrm{pair}}d_j\le MD_j d j T Ψ pair d j ≤ M D j with D j : = ∥ d j ∥ 2 2 = 1 + ∥ ζ ∥ 2 2 ∈ ( 1 , 2 ] D_j := \lVert d_j\rVert_2^2 = 1 + \lVert\zeta\rVert_2^2 \in(1,2] D j := ∥ d j ∥ 2 2 = 1 + ∥ ζ ∥ 2 2 ∈ ( 1 , 2 ] . Optimising over α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] : if g j ≤ M D j g_j \le MD_j g j ≤ M D j , take α = g j / ( M D j ) \alpha= g_j/(MD_j) α = g j / ( M D j ) to get a gain of at least g j 2 / ( 2 M D j ) ≥ g j 2 / ( 4 M ) g_j^2/(2MD_j) \ge g_j^2/(4M) g j 2 / ( 2 M D j ) ≥ g j 2 / ( 4 M ) ; if g j > M D j g_j > MD_j g j > M D j , take α = 1 \alpha= 1 α = 1 to get a gain of at least g j − M D j / 2 > g j / 2 g_j - MD_j/2 > g_j/2 g j − M D j /2 > g j /2 . Hence
f ( L ∪ { j } ) − f ( L ) ≥ ϕ j : = min { ( g j + ) 2 4 M , g j + 2 } for every j ∈ S , (18) f(\mathcal{L} \cup\{j\}) - f(\mathcal{L}) \ge\phi_j := \min\left\{\frac{(g_j^+)^2}{4M}, \frac{g_j^+}{2}\right\} \quad\text{for every } j \in S, \tag*{(18)} f ( L ∪ { j }) − f ( L ) ≥ ϕ j := min { 4 M ( g j + ) 2 , 2 g j + } for every j ∈ S , (18)
which holds trivially (with ϕ j = 0 \phi_j = 0 ϕ j = 0 ) when g j ≤ 0 g_j \le0 g j ≤ 0 , by monotonicity.
Step 4 (combining). If g max ≤ 2 M g_{\max} \le2M g m a x ≤ 2 M , then for every j j j , g j + / 2 ≥ ( g j + ) 2 / ( 4 M ) g_j^+/2 \ge(g_j^+)^2/(4M) g j + /2 ≥ ( g j + ) 2 / ( 4 M ) , so ∑ j ∈ S ϕ j ≥ ∥ g S + ∥ 2 2 / ( 4 M ) ≥ m 2 M ∥ g S + ∥ 2 2 2 m \sum_{j\in S}\phi_j \ge\lVert g_S^+\rVert_2^2/(4M) \ge\frac{m}{2M}\frac{\lVert g_S^+\rVert_2^2}{2m} ∑ j ∈ S ϕ j ≥ ∥ g S + ∥ 2 2 / ( 4 M ) ≥ 2 M m 2 m ∥ g S + ∥ 2 2 . If g max > 2 M g_{\max} > 2M g m a x > 2 M , the maximising j ∗ j^* j ∗ satisfies g j ∗ > 2 M ≥ M D j ∗ g_{j^*} > 2M \ge MD_{j^*} g j ∗ > 2 M ≥ M D j ∗ , so ∑ j ∈ S ϕ j ≥ g max / 2 ≥ 1 2 g max ≥ m 2 M g max \sum_{j\in S}\phi_j \ge g_{\max}/2 \ge\frac{1}{2}g_{\max} \ge\frac{m}{2M}g_{\max} ∑ j ∈ S ϕ j ≥ g m a x /2 ≥ 2 1 g m a x ≥ 2 M m g m a x , using m ≤ M m \le M m ≤ M . In both cases, by (17) ,
∑ j ∈ S [ f ( L ∪ { j } ) − f ( L ) ] ≥ m ∣ L ∣ + ∣ S ∣ 2 M ∣ L ∣ + 1 [ f ( L ∪ S ) − f ( L ) ] , \sum_{j\in S}\left[f(\mathcal{L}\cup\{j\})-f(\mathcal{L})\right] \ge\frac{m|\mathcal{L}|+|S|}{2M|\mathcal{L}|+1}\left[f(\mathcal{L}\cup S)-f(\mathcal{L})\right], j ∈ S ∑ [ f ( L ∪ { j }) − f ( L ) ] ≥ 2 M ∣ L ∣ + 1 m ∣ L ∣ + ∣ S ∣ [ f ( L ∪ S ) − f ( L ) ] ,
which is the claimed bound on γ L , S \gamma_{\mathcal{L},S} γ L , S . The bound in terms of τ \tau τ follows from (15) , after the factor λ \lambda λ cancels.
Corollary 1 (Greedy guarantee). Let τ > τ c \tau> \tau_c τ > τ c and let greedy start from A 1 = { a 1 } A_1 = \{a_1\} A 1 = { a 1 } with a 1 ∈ arg max j f ( { j } ) a_1 \in\arg\max_j f(\{j\}) a 1 ∈ arg max j f ({ j }) , then add A t + 1 = A t ∪ { arg max j f ( A t ∪ { j } ) } A_{t+1} = A_t \cup\{\arg\max_j f(A_t \cup\{j\})\} A t + 1 = A t ∪ { arg max j f ( A t ∪ { j })} . Let O P T r : = max ∣ A ∣ ≤ r , A ≠ ∅ f ( A ) \mathrm{OPT}_r := \max_{|A|\le r,\ A\ne\emptyset} f(A) OPT r := max ∣ A ∣ ≤ r , A = ∅ f ( A ) and γ k : = m 2 k − 1 / ( 2 M k + 1 ) \gamma_k := m2^{k-1}/(2M^{k+1}) γ k := m 2 k − 1 / ( 2 M k + 1 ) . Then for every k ≥ 2 k \ge2 k ≥ 2
f ( A k ) − f ( A 1 ) ≥ ( 1 − e − γ k ) ( O P T k − 1 − f ( A 1 ) ) . f(A_k)-f(A_1) \ge\left(1-e^{-\gamma_k}\right)\left(\mathrm{OPT}_{k-1}-f(A_1)\right). f ( A k ) − f ( A 1 ) ≥ ( 1 − e − γ k ) ( OPT k − 1 − f ( A 1 ) ) .
Proof. On V ∖ { a 1 } \mathcal{V}\setminus\{a_1\} V ∖ { a 1 } define g ( T ) : = f ( T ∪ { a 1 } ) − f ( { a 1 } ) g(T):=f(T\cup\{a_1\})-f(\{a_1\}) g ( T ) := f ( T ∪ { a 1 }) − f ({ a 1 }) . Then g ( ∅ ) = 0 g(\emptyset)=0 g ( ∅ ) = 0 , and g g g is monotone by Lemma 1. Greedy on f f f after step 1 is greedy on g g g . For T ⊆ A k ∖ { a 1 } T\subseteq A_k\setminus\{a_1\} T ⊆ A k ∖ { a 1 } and ∣ S ∣ ≤ k − 1 |S|\le k-1 ∣ S ∣ ≤ k − 1 , the ratio γ T , S g = γ T ∪ { a 1 } , S f \gamma^g_{T,S}=\gamma^f_{T\cup\{a_1\},S} γ T , S g = γ T ∪ { a 1 } , S f , and Theorem 1 bounds it below by γ k \gamma_k γ k , since ∣ T ∪ { a 1 } ∣ + ∣ S ∣ ≤ 2 k − 1 |T\cup\{a_1\}|+|S|\le2k-1 ∣ T ∪ { a 1 } ∣ + ∣ S ∣ ≤ 2 k − 1 and ∣ T ∪ { a 1 } ∣ + 1 ≤ k + 1 |T\cup\{a_1\}|+1\le k+1 ∣ T ∪ { a 1 } ∣ + 1 ≤ k + 1 . The greedy bound for weakly submodular functions [11 , 15 ] gives g ( A k ∖ { a 1 } ) ≥ ( 1 − e − γ k ) max ∣ T ∣ ≤ k − 1 g ( T ) g(A_k\setminus\{a_1\})\ge(1-e^{-\gamma_k})\max_{|T|\le k-1}g(T) g ( A k ∖ { a 1 }) ≥ ( 1 − e − γ k ) max ∣ T ∣ ≤ k − 1 g ( T ) . For any A ∗ A^* A ∗ with ∣ A ∗ ∣ ≤ k − 1 |A^*|\le k-1 ∣ A ∗ ∣ ≤ k − 1 , monotonicity gives max ∣ T ∣ ≤ k − 1 g ( T ) ≥ f ( A ∗ ∪ { a 1 } ) − f ( { a 1 } ) ≥ f ( A ∗ ) − f ( { a 1 } ) \max_{|T|\le k-1}g(T)\ge f(A^*\cup\{a_1\})-f(\{a_1\})\ge f(A^*)-f(\{a_1\}) max ∣ T ∣ ≤ k − 1 g ( T ) ≥ f ( A ∗ ∪ { a 1 }) − f ({ a 1 }) ≥ f ( A ∗ ) − f ({ a 1 }) .
Remark 3 (Relation to the plotted curvature ratio). The empirical curvature curves report λ min ( ( S + τ I ) A ) / λ max ( ( S + τ I ) A ) \lambda_{\min}((S+\tau I)_A)/\lambda_{\max}((S+\tau I)_A) λ m i n (( S + τ I ) A ) / λ m a x (( S + τ I ) A ) , the ratio of unrestricted principal-submatrix eigenvalues. Restricting the Rayleigh quotient to 1 ⊥ 1^\perp 1 ⊥ can only raise the minimum and lower the maximum, so this ratio is a conservative proxy for the constants in Theorem 1 (up to the factor 2). By (15) the restricted constants stay positive at every support size for any τ > τ c \tau>\tau_c τ > τ c ; a negative proxy therefore does not imply that the guarantee fails.
Weak submodularity in numbers and an empirical check
The guarantee in numbers. With τ = τ 0 \tau=\tau_0 τ = τ 0 , the zero-sum curvature constants of S + τ I S+\tau I S + τ I are m = τ 0 − τ c = 169.21 m=\tau_0-\tau_c=169.21 m = τ 0 − τ c = 169.21 and M = λ max ( U ⊤ S U ) + τ 0 = 24.80 + 186.30 = 211.10 M=\lambda_{\max}(U^\top S U)+\tau_0=24.80+186.30=211.10 M = λ m a x ( U ⊤ S U ) + τ 0 = 24.80 + 186.30 = 211.10 . Theorem 1 then gives γ ≥ m / ( 2 M ) = 0.40 \gamma\ge m/(2M)=0.40 γ ≥ m / ( 2 M ) = 0.40 , so k k k -step greedy attains at least 1 − e − 0.40 ≈ 0.33 1-e^{-0.40}\approx0.33 1 − e − 0.40 ≈ 0.33 of the best ( k − 1 ) (k-1) ( k − 1 ) -task value. This is a worst-case bound over all supports. Empirically γ ^ ≥ 1 \hat{\gamma}\ge1 γ ^ ≥ 1 on every sampled pair (Figure 6c ).
Empirical check of weak submodularity. We run exact greedy on f f f (Equation (6) ), re-solving f ( A ∪ { j } ) f(\mathcal{A}\cup\{j\}) f ( A ∪ { j }) for every candidate j j j at each step, and compare it with 5 random insertion orders (seeds 0–4). We estimate the submodularity ratio [11 ] for τ ∈ { τ 0 , 50 , 0 } \tau\in\{\tau_0,50,0\} τ ∈ { τ 0 , 50 , 0 } on two families of disjoint pairs ( A , S ) (\mathcal{A},S) ( A , S ) (Figure 6c ). Greedy prefixes (880 pairs): A \mathcal{A} A is the first a ∈ { 1 , 2 , 5 , 10 , 25 , 50 , 100 , 150 , 200 , 250 } a\in\{1,2,5,10,25,50,100,150,200,250\} a ∈ { 1 , 2 , 5 , 10 , 25 , 50 , 100 , 150 , 200 , 250 } greedy tasks and ∣ S ∣ ∈ { 2 , 5 , 10 , 25 } |S|\in\{2,5,10,25\} ∣ S ∣ ∈ { 2 , 5 , 10 , 25 } , with S S S drawn uniformly over 20 times plus two adversarial choices (the next ∣ S ∣ |S| ∣ S ∣ greedy tasks and the ∣ S ∣ |S| ∣ S ∣ tasks with the largest individual gains). Random sets (180 pairs): 12 uniform draws of A \mathcal{A} A for each ∣ A ∣ ∈ { 1 , 3 , 10 , 30 , 100 } |\mathcal{A}|\in\{1,3,10,30,100\} ∣ A ∣ ∈ { 1 , 3 , 10 , 30 , 100 } , with ∣ S ∣ ∈ { 2 , 5 , 10 } |S|\in\{2,5,10\} ∣ S ∣ ∈ { 2 , 5 , 10 } . We discard pairs where S S S adds nothing to A \mathcal{A} A (denominator of (1) below 10 − 10 10^{-10} 1 0 − 10 ). At τ = 0 \tau=0 τ = 0 , f f f is non-convex, so we take the best of the warm start, four Dirichlet restarts and every single-task vertex of A \mathcal{A} A ; its γ ^ \hat{\gamma} γ ^ is therefore approximate. Findings. (i) Greedy gains are non-increasing at all 307 steps. (ii) Greedy reaches 91% of the total gain by k = 10 k=10 k = 10 , 98.9% by k = 50 k=50 k = 50 and f ( V ) f(\mathcal{V}) f ( V ) at k ≈ 206 k\approx206 k ≈ 206 ; random orders reach f ( V ) f(\mathcal{V}) f ( V ) only near k = n k=n k = n . (iii) No retained pair has γ ^ < 1 \hat{\gamma}<1 γ ^ < 1 . At τ 0 \tau_0 τ 0 , 742/880 and 180/180 pairs are retained (median γ ^ \hat{\gamma} γ ^ 1.30 and 1.28); at τ = 50 \tau=50 τ = 50 , 577/880 and 179/180 (medians 1.36, 1.26); at τ = 0 \tau=0 τ = 0 , 0/880 and 75/180 (median 1.34). (iv) The conservative proxy λ min / λ max \lambda_{\min}/\lambda_{\max} λ m i n / λ m a x of ( S + τ I ) A (S + \tau I)_A ( S + τ I ) A , the principal submatrix of S + τ I S + \tau I S + τ I with rows and columns indexed by A \mathcal{A} A (Figure 6d ), stays above 0.44 for ∣ A ∣ ≤ 250 |\mathcal{A}| \le250 ∣ A ∣ ≤ 250 at τ 0 \tau_0 τ 0 , falls to 4 × 10 − 6 4 \times10^{-6} 4 × 1 0 − 6 at ∣ A ∣ = n |\mathcal{A}| = n ∣ A ∣ = n , and is negative throughout at τ = 0 \tau= 0 τ = 0 . The exact zero-sum constants, however, stay positive at every support size whenever τ > τ c \tau> \tau_c τ > τ c , so the guarantee covers the whole greedy path at τ 0 \tau_0 τ 0 and τ = 50 \tau= 50 τ = 50 . At τ = 0 < τ c \tau= 0 < \tau_c τ = 0 < τ c there is no guarantee: γ ^ ≥ 1 \widehat{\gamma} \ge1 γ ≥ 1 holds only because f f f collapses to the best single task in A \mathcal{A} A , and greedy returns that one task. The shift is what makes the selected set non-degenerate.
Mixture Design: Spectrum Shift, Convexity and the Operating Point
This section explains, step by step, how the single mixture p ∗ p^* p ∗ used in every fine-tuning experiment is obtained from the affinity matrix S S S . Section C.1 motivates the objective, Section C.2 rewrites it as a projection, Section C.3 explains why a diagonal shift is needed and how large it must be, Section C.4 explains how the trade-off ratio ρ \rho ρ controls coverage and fixes the operating point, Section C.5 describes and verifies the solver, and Section C.6 turns the mixture into a training set. Throughout, d : = S 1 \boldsymbol{d} := S\mathbf{1} d := S 1 denotes the vector of task degrees (d [ i ] = S [ i ] d_{[i]} = S_{[i]} d [ i ] = S [ i ] in the main text).
Design rationale
Why both potentials derive from the same affinity graph. Deriving representativeness and redundancy from a single similarity matrix is deliberate and follows a well-established design in subset selection. Graph-centrality summarization scores sentences by their degree in a similarity graph, and coverage–diversity objectives for extractive summarization and data subset selection likewise compute both the coverage reward and the redundancy penalty from one similarity kernel. Three considerations motivate this choice here. (i) Consistency : if representativeness and redundancy were measured with different notions of similarity, a task could be judged central under one and non-redundant under the other for incompatible reasons; a single behavioral S S S guarantees the tradeoff is internally coherent. (ii) No target leakage : every quantity is computed from the training pool alone, so the resulting mixture is benchmark-independent by construction, which is precisely what enables a single general-purpose checkpoint. (iii) Interpretability : as we show next, sharing S S S yields a closed-form characterization with a single, meaningful control knob.
Reading the affinity. S [ i j ] S_{[ij]} S [ ij ] is the symmetrised average log-likelihood ratio between the single-task models of T i \mathcal{T}_i T i and T j \mathcal{T}_j T j , each evaluated on the other’s held-out data (Equation (5) ). It is pointwise mutual information in the sense of [7 ] , between the task identity and the observed response, not mutual information between two random variables. Because each model fits its own task best, 95% of the off-diagonal entries are negative (mean − 0.43 -0.43 − 0.43 ), and every degree d [ i ] \boldsymbol{d}_{[i]} d [ i ] is negative, ranging from − 1241 -1241 − 1241 to − 3.4 -3.4 − 3.4 . A task is therefore representative when its degree is least negative : the other tasks’ models predict its data almost as well as its own model does. By the offset invariance below, only differences between degrees matter.
Restoring self-affinity. Both scores in (5) are defined between distinct tasks , so we set S ~ [ i i ] = 0 \widetilde{S}_{[ii]}=0 S [ ii ] = 0 . A hollow matrix has zero trace and is therefore indefinite (unless S = 0 S=0 S = 0 ), which makes the quadratic in (3) nonconvex. This is an artifact of leaving the diagonal empty rather than a property of the tasks: every task is, trivially, maximally similar to itself. We therefore restore a uniform self-affinity S ~ = S + τ I \widetilde{S}=S+\tau I S = S + τ I as in (20) . This is the spectrum shift of [6 , 42 ] , now read as filling the missing diagonal. Replacing S S S by S ~ \widetilde{S} S in both potentials changes Ψ u n \Psi_{\mathrm{un}} Ψ un only by the constant vector β τ 1 n \beta\tau\mathbf{1}_n β τ 1 n , which is constant on Δ n \Delta_n Δ n and hence does not affect the minimizer. The net effect is the pairwise term λ τ 2 ∥ p ∥ 2 2 \frac{\lambda\tau}{2}\lVert p\rVert_2^2 2 λ τ ∥ p ∥ 2 2 , a preference for spreading mass that is consistent with the diversity goal. Positive definiteness on all of R n \mathbb{R}^n R n (τ > τ 0 \tau>\tau_0 τ > τ 0 ) makes Proposition 1 a projection in a norm, while convexity on Δ n \Delta_n Δ n needs only τ > τ c \tau>\tau_c τ > τ c (Lemma 1). Without any diagonal the problem is non-convex on Δ n \Delta_n Δ n and its optimum collapses onto a single task (Figure 2 ).
A single general-purpose checkpoint vs. per-target selection. Per-target methods such as LESS select a different subset, and train a different model, for each benchmark using that benchmark’s data. TaskMixPGM produces one mixture and one checkpoint evaluated on every benchmark. The affinities are computed once per task pool and reused for every budget and base model (Section D.1), whereas a gradient datastore must be rebuilt per base model and the selection repeated per benchmark.
Mixture design as an affinity-geometry projection
Objective. Let S ∈ R n × n S\in\mathbb{R}^{n\times n} S ∈ R n × n be the symmetric, hollow PMI task-affinity matrix and Δ n = { p ∈ R ≥ 0 n : 1 T p = 1 } \Delta_n=\{p\in\mathbb{R}_{\geq0}^n:\mathbf{1}^{\mathsf{T}}p=1\} Δ n = { p ∈ R ≥ 0 n : 1 T p = 1 } . With Ψ u n = β S ~ 1 \Psi_{\mathrm{un}}=\beta\widetilde{S}\mathbf{1} Ψ un = β S 1 and Ψ p a i r = λ S ~ \Psi_{\mathrm{pair}}=\lambda\widetilde{S} Ψ pair = λ S , Equation (3) reads
p ∗ = arg min p ∈ Δ n − β 1 T S ~ p + λ 2 p T S ~ p (19) p^*=\underset{p\in\Delta_n}{\arg\min}\;-\beta\mathbf{1}^{\mathsf{T}}\widetilde{S}p+\frac{\lambda}{2}p^{\mathsf{T}}\widetilde{S}p \tag*{(19)} p ∗ = p ∈ Δ n arg min − β 1 T S p + 2 λ p T S p (19)
S ~ = S + τ I . (20) \widetilde{S}=S+\tau I. \tag*{(20)} S = S + τ I . (20)
Two observations fix the meaning of τ \tau τ . First, on Δ n \Delta_n Δ n the unary term differs from − β 1 T S p -\beta\mathbf{1}^{\mathsf{T}}Sp − β 1 T S p only by the constant β τ \beta\tau β τ , so the diagonal does not alter representativeness. Second, p T S ~ p = p T S p + τ ∥ p ∥ 2 p^{\mathsf{T}}\widetilde{S}p=p^{\mathsf{T}}Sp+\tau\lVert p\rVert^2 p T S p = p T S p + τ ∥ p ∥ 2 , and ∥ p ∥ 2 \lVert p\rVert^2 ∥ p ∥ 2 is the collision probability of p p p (the inverse of its order-2 effective size), so τ \tau τ acts as a quadratic-entropy (diversity) regulariser on the mixture.
Proposition 1 (Mixture design as affinity-geometry projection). Let S ~ ≻ 0 \widetilde{S}\succ0 S ≻ 0 , ρ : = β / λ \rho:=\beta/\lambda ρ := β / λ , and ∥ x ∥ S ~ 2 : = x T S ~ x \lVert x\rVert_{\widetilde{S}}^2:=x^{\mathsf{T}}\widetilde{S}x ∥ x ∥ S 2 := x T S x . Then, for all p ∈ R n p\in\mathbb{R}^n p ∈ R n ,
− β 1 T S ~ p + λ 2 p T S ~ p = λ 2 ∥ p − ρ 1 n ∥ S ~ 2 − β 2 2 λ 1 T S ~ 1. -\beta\mathbf{1}^{\mathsf{T}}\widetilde{S}p+\frac{\lambda}{2}p^{\mathsf{T}}\widetilde{S}p=\frac{\lambda}{2}\lVert p-\rho\mathbf{1}_n\rVert_{\widetilde{S}}^2-\frac{\beta^2}{2\lambda}\mathbf{1}^{\mathsf{T}}\widetilde{S}\mathbf{1}. − β 1 T S p + 2 λ p T S p = 2 λ ∥ p − ρ 1 n ∥ S 2 − 2 λ β 2 1 T S 1 . so the optimal mixture is the unique S ~ \widetilde{S} S -projection of the scaled uniform allocation ρ 1 n \rho\mathbf{1}_n ρ 1 n onto the simplex:
p ⋆ = arg min p ∈ Δ n ∥ p − ρ 1 n ∥ S ~ . p^\star=\underset{p\in\Delta_n}{\operatorname{arg\,min}}\ \lVert p-\rho\mathbf{1}_n\rVert_{\widetilde{S}}. p ⋆ = p ∈ Δ n arg min ∥ p − ρ 1 n ∥ S . Proof. Expand the right-hand side using the symmetry of S ~ \widetilde{S} S and λ ρ = β \lambda\rho=\beta λ ρ = β ; the constant does not depend on p p p . Since S ~ ≻ 0 \widetilde{S}\succ0 S ≻ 0 , ∥ ⋅ ∥ S ~ 2 \lVert\cdot\rVert_{\widetilde{S}}^2 ∥ ⋅ ∥ S 2 is strictly convex and Δ n \Delta_n Δ n is compact and convex, so the minimiser exists and is unique.
Corollary 2 (Uniform ↔ \leftrightarrow ↔ minimum-redundancy interpolation). Let u = 1 n 1 n u=\frac{1}{n}\mathbf{1}_n u = n 1 1 n be the uniform mixture and
q : = arg min p : 1 T p = 1 p T S ~ p = S ~ − 1 1 n 1 T S ~ − 1 1 n q:=\underset{p:\mathbf{1}^{\mathsf{T}}p=1}{\operatorname{arg\,min}}\ p^{\mathsf{T}}\widetilde{S}p=\frac{\widetilde{S}^{-1}\mathbf{1}_n}{\mathbf{1}^{\mathsf{T}}\widetilde{S}^{-1}\mathbf{1}_n} q := p : 1 T p = 1 arg min p T S p = 1 T S − 1 1 n S − 1 1 n be the minimum-redundancy mixture. The stationary point of (19) under the equality constraint alone is
p ~ = n ρ u − ( n ρ − 1 ) q . \widetilde{p}=n\rho u-(n\rho-1)q. p = n ρ u − ( n ρ − 1 ) q . Hence ρ = 1 / n \rho=1/n ρ = 1/ n returns the uniform mixture (p ~ = u ∈ Δ n \widetilde{p}=u\in\Delta_n p = u ∈ Δ n , so p ⋆ = u p^\star=u p ⋆ = u ); ρ < 1 / n \rho<1/n ρ < 1/ n gives a convex combination of u u u and q q q (diversity); and ρ > 1 / n \rho>1/n ρ > 1/ n extrapolates from u u u away from q q q (representativeness). The nonnegativity constraint then determines the support of p ⋆ p^\star p ⋆ .
Proof. Stationarity gives λ S ~ p = β S ~ 1 − ν ′ 1 \lambda\widetilde{S}p=\beta\widetilde{S}\mathbf{1}-\nu'\mathbf{1} λ S p = β S 1 − ν ′ 1 , i.e. p = ρ 1 − ( ν ′ / λ ) S ~ − 1 1 p=\rho\mathbf{1}-(\nu'/\lambda)\widetilde{S}^{-1}\mathbf{1} p = ρ 1 − ( ν ′ / λ ) S − 1 1 . Imposing 1 T p = 1 \mathbf{1}^{\mathsf{T}}p=1 1 T p = 1 gives ν ′ / λ = ( n ρ − 1 ) / ( 1 T S ~ − 1 1 ) \nu'/\lambda=(n\rho-1)/(\mathbf{1}^{\mathsf{T}}\widetilde{S}^{-1}\mathbf{1}) ν ′ / λ = ( n ρ − 1 ) / ( 1 T S − 1 1 ) , and substituting yields the claim.
Remark What q q q down-weights In general q q q need not be ordered by task degree d d d . When the diagonal dominates (∥ S ∥ 2 < τ \lVert S\rVert^2<\tau ∥ S ∥ 2 < τ ), the Neumann series gives S ~ − 1 1 = τ − 1 ( 1 − τ − 1 d ) + O ( ∥ S ∥ 2 / τ 3 ) \widetilde{S}^{-1}\mathbf{1}=\tau^{-1}(\mathbf{1}-\tau^{-1}d)+O(\lVert S\rVert^2/\tau^3) S − 1 1 = τ − 1 ( 1 − τ − 1 d ) + O (∥ S ∥ 2 / τ 3 ) , so to first order q q q down-weights high-degree tasks and p ~ \widetilde{p} p for ρ > 1 / n \rho>1/n ρ > 1/ n up-weights them. At the operating point (τ = τ 0 + 10 − 3 \tau=\tau_0+10^{-3} τ = τ 0 + 1 0 − 3 , n ρ = 7.49 n\rho=7.49 n ρ = 7.49 ) the ordering is nearly exact: Spearman ( q , d ) = − 0.994 \operatorname{Spearman}(q,d)=-0.994 Spearman ( q , d ) = − 0.994 and Spearman ( p ~ , d ) = 0.994 \operatorname{Spearman}(\widetilde{p},d)=0.994 Spearman ( p , d ) = 0.994 .
Remark Connection to mean–variance portfolio design Reading S ~ \widetilde{S} S as a covariance, q q q is the global minimum-variance portfolio and Corollary 2 is the two-fund separation theorem: every equality-constrained solution is an affine combination of the two funds u u u and q q q . The simplex constraint is the usual long-only (no short-selling) restriction, and ρ \rho ρ plays the role of the return–risk trade-off.
How much shift is needed: τ 0 \tau_0 τ 0 versus τ c \tau_c τ c
Two thresholds. Problem (19) is optimised over Δ n \Delta_n Δ n , whose affine hull has direction space 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ . Strict convexity therefore requires positive definiteness of S ~ \widetilde{S} S only on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , not on R n \mathbb{R}^n R n .
Lemma 1 (Convexity on the simplex). Let B ∈ R n × ( n − 1 ) B\in\mathbb{R}^{n\times(n-1)} B ∈ R n × ( n − 1 ) have orthonormal columns spanning 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ and define
τ 0 : = − λ min ( S ) , τ c : = − λ min ( B T S B ) ≤ τ 0 . \tau_0:=-\lambda_{\min}(S),\qquad\tau_c:=-\lambda_{\min}(B^{\mathsf{T}}SB)\leq\tau_0. τ 0 := − λ m i n ( S ) , τ c := − λ m i n ( B T S B ) ≤ τ 0 . The objective (19) is strictly convex on Δ n \Delta_n Δ n if and only if τ > τ c \tau>\tau_c τ > τ c , and S ~ ≻ 0 \widetilde{S}\succ0 S ≻ 0 if and only if τ > τ 0 \tau>\tau_0 τ > τ 0 .
Proof. For p , p + h ∈ Δ n p,p+h\in\Delta_n p , p + h ∈ Δ n we have h ∈ 1 ⊥ h\in\mathbf{1}^{\perp} h ∈ 1 ⊥ , and the second-order term of (19) along h h h is λ 2 h T S ~ h = λ 2 z T ( B T S B + τ I ) z \frac{\lambda}{2}h^{\mathsf{T}}\widetilde{S}h=\frac{\lambda}{2}z^{\mathsf{T}}(B^{\mathsf{T}}SB+\tau I)z 2 λ h T S h = 2 λ z T ( B T S B + τ I ) z with h = B z h=Bz h = B z . This is positive for all z ≠ 0 z\neq0 z = 0 if τ > τ c \tau>\tau_c τ > τ c [?]. The second claim is immediate, and τ c ≤ τ 0 \tau_c\leq\tau_0 τ c ≤ τ 0 by Cauchy interlacing.
(B B B plays the role of U U U in the main text, Equation (4) ). Three regimes follow. For τ > τ 0 \tau>\tau_0 τ > τ 0 the objective is strictly convex on R n \mathbb{R}^n R n and Proposition 1 is a projection in a norm. For τ c < τ ≤ τ 0 \tau_c<\tau\leq\tau_0 τ c < τ ≤ τ 0 the minimiser over
Δ n \Delta_n Δ n is still unique, the identity of Proposition 1 still holds algebraically, and ∥ ⋅ ∥ S ~ \lVert\cdot\rVert_{\widetilde S} ∥ ⋅ ∥ S is a norm on 1 ⊥ 1^\perp 1 ⊥ only; Corollary 2 holds wherever S ~ \widetilde S S is nonsingular, since it uses only the equality-constrained KKT system. For τ ≤ τ c \tau\le\tau_c τ ≤ τ c the problem is non-convex on Δ n \Delta_n Δ n and projected gradient may stop at different local minima.
Why τ c ≪ τ 0 \tau_c \ll\tau_0 τ c ≪ τ 0 : the spectrum of S S S . For our affinity matrix, τ 0 = 186.30 \tau_0 = 186.30 τ 0 = 186.30 but τ c = 17.09 \tau_c = 17.09 τ c = 17.09 , an order of magnitude smaller (Figure 7 ). S S S has 206 positive and 103 negative eigenvalues, λ max = 57.68 \lambda_{\max} = 57.68 λ m a x = 57.68 , and a single negative outlier, λ min = − 186.30 \lambda_{\min} = -186.30 λ m i n = − 186.30 ; the next eigenvalue is − 15.42 -15.42 − 15.42 . The outlier alone carries 86.8% of ∥ S ∥ F 2 \lVert S\rVert_F^2 ∥ S ∥ F 2 . Its eigenvector v min v_{\min} v m i n satisfies v min T 1 / n = 0.884 v_{\min}^{\mathsf T}1/\sqrt{n} = 0.884 v m i n T 1/ n = 0.884 (cos 2 = 0.78 \cos^2 = 0.78 cos 2 = 0.78 ): it lies mostly along 1 1 1 , the one direction that is fixed on Δ n \Delta_n Δ n , and it loads almost uniformly on every task (Figure 8 ). Every other eigenvector is essentially orthogonal to 1 1 1 (cos 2 ≤ 2.7 × 10 − 3 \cos^2 \le2.7 \times10^{-3} cos 2 ≤ 2.7 × 1 0 − 3 , below the 1 / n 1/n 1/ n expected for a random direction). Restricting S S S to 1 ⊥ 1^\perp 1 ⊥ removes the outlier (Figure 7 c), so the PSD threshold τ 0 \tau_0 τ 0 is driven by a direction the optimisation never moves in.
Figure 7. Eigen-structure of the PMI affinity matrix S S S (n = 309 n = 309 n = 309 ). (a) Sorted eigenvalues (blue: positive, orange: negative), with an inset on ranks 6–304. S S S is strongly indefinite, with one outlier λ min = − τ 0 = − 186.3 \lambda_{\min} = -\tau_0 = -186.3 λ m i n = − τ 0 = − 186.3 ; the next eigenvalue is − 15.4 -15.4 − 15.4 . (b) Fraction of ∥ S ∥ F 2 \lVert S\rVert_F^2 ∥ S ∥ F 2 captured by the k k k largest-magnitude eigenpairs. The outlier alone carries 86.8%; 2 eigenpairs give 90% and 13 give 99% (entropy effective rank 28.5). (c) The 10 smallest eigenvalues of S S S and of its restriction B T S B B^{\mathsf T}SB B T S B to 1 ⊥ 1^\perp 1 ⊥ . Restriction removes the outlier and raises the threshold from − τ 0 = − 186.3 -\tau_0 = -186.3 − τ 0 = − 186.3 to − τ c = − 17.1 -\tau_c = -17.1 − τ c = − 17.1 .
Figure 8. (a) cos 2 ( v i , 1 ) \cos^2(\boldsymbol{v}_i,\mathbf{1}) cos 2 ( v i , 1 ) against λ i \lambda_i λ i for all 309 eigenvectors of S S S (dashed: 1 / n 1/n 1/ n ). Only v min \boldsymbol{v}_{\min} v m i n (0.78) and v max \boldsymbol{v}_{\max} v m a x (0.21) are substantially aligned with 1 \mathbf{1} 1 . (b) Loadings of v min \boldsymbol{v}_{\min} v m i n and v max \boldsymbol{v}_{\max} v m a x by source collection (dashed: 1 / n 1/\sqrt{n} 1/ n , the loading of a uniform vector). v min \boldsymbol{v}_{\min} v m i n is close to uniform for T0, Flan, CoT and Tulu (larger on SuperGLUE), while v max \boldsymbol{v}_{\max} v m a x separates SuperGLUE from the other collections.
Offset invariance. This is the spectral face of the invariance in § 3.1 : replacing S S S by S + c 11 T S + c11^{\mathsf T} S + c 1 1 T changes (19) by a constant on Δ n \Delta_n Δ n and leaves τ c \tau_c τ c unchanged, while λ min ( S + c 11 T ) → − τ c \lambda_{\min}(S + c11^{\mathsf T}) \to-\tau_c λ m i n ( S + c 1 1 T ) → − τ c as c → ∞ c \to\infty c → ∞ . The PMI scores carry such an offset (mean entry − 0.43 -0.43 − 0.43 ), but it is not uniform across rows: subtracting only the mean entry raises λ min \lambda_{\min} λ m i n from − 186.3 -186.3 − 186.3 to − 98.6 -98.6 − 98.6 , and the full restriction to 1 ⊥ 1^\perp 1 ⊥ is needed to reach − τ c -\tau_c − τ c .
What the shift does to the mixture. Figure 2 in the main text reports p ∗ ( τ ) p^*(\tau) p ∗ ( τ ) as τ \tau τ decreases from τ 0 \tau_0 τ 0 at fixed ρ \rho ρ . The mixture contracts smoothly: its support falls from 206 tasks at τ 0 \tau_0 τ 0 to 165, 123 and 67 at τ = 100 \tau= 100 τ = 100 , 50 and τ c + \tau_c^+ τ c + , and its effective size e H ( p ∗ ) e^{H(p^*)} e H ( p ∗ ) from 179.6 to 44.6, while the collection-level allocation stays stable (T0 receives 0.62–0.65 of the mass; Figure 9 ). Without any shift (τ = 0 \tau= 0 τ = 0 ) the problem is non-convex on Δ n \Delta_n Δ n : projected gradient from 28 initialisations (uniform, p ∗ ( τ 0 ) p^*(\tau_0) p ∗ ( τ 0 ) , 20 Dirichlet draws, single-task vertices) always ends at a single-task vertex, 27 of them at the same task (FLAN2021 MATH_DATASET_ALGEBRA_LINEAR_1D), at TV ( p ∗ ( 0 ) , p ∗ ( τ 0 ) ) = 0.985 \operatorname{TV}(p^*(0), p^*(\tau_0)) = 0.985 TV ( p ∗ ( 0 ) , p ∗ ( τ 0 )) = 0.985 . Removing the shift is therefore not a meaningful ablation of the mixture; it changes the problem from a unique, broad minimiser to an order-dependent single task.
The shift we use. All experiments use τ = τ 0 + 10 − 3 = 186.30 \tau= \tau_0 + 10^{-3} = 186.30 τ = τ 0 + 1 0 − 3 = 186.30 , the smallest shift for which S ~ ≻ 0 \widetilde S \succ0 S ≻ 0 . This keeps Proposition 1 valid verbatim, gives the broadest mixture among the convex choices at a fixed ρ \rho ρ , and leaves the breadth of the mixture to be set by ρ \rho ρ alone (Section C.4). Any τ ∈ ( τ c , τ 0 ] \tau\in(\tau_c,\tau_0] τ ∈ ( τ c , τ 0 ] also yields a unique mixture; smaller τ \tau τ gives a sparser one.
The trade-off ratio ρ \rho ρ as a coverage control
Only the ratio matters. Dividing (19) by λ \lambda λ leaves the minimiser unchanged, so p ∗ p^* p ∗ depends on β \beta β and λ \lambda λ only through ρ = β / λ \rho= \beta/\lambda ρ = β / λ , and we set ρ \rho ρ directly. By Proposition 1, p ∗ p^* p ∗ is the point of Δ n \Delta_n Δ n closest to ρ 1 \rho1 ρ 1 in the affinity geometry, so ρ \rho ρ is the per-task mass the objective would like every task to receive. Its natural unit is 1 / n 1/n 1/ n : n ρ n\rho n ρ is the total mass requested, relative to the one unit the simplex can provide.
How n ρ n\rho n ρ controls coverage. Corollary 2 gives the picture. At n ρ = 1 n\rho= 1 n ρ = 1 the request is exactly feasible and p ∗ = u \boldsymbol{p}^* = \boldsymbol{u} p ∗ = u : every task is covered equally. For n ρ > 1 n\rho> 1 n ρ > 1 the request exceeds the budget by a factor n ρ n\rho n ρ , the unconstrained solution p ~ = n ρ u − ( n ρ − 1 ) q \widetilde{\boldsymbol{p}} = n\rho\boldsymbol{u}-(n\rho-1)\boldsymbol{q} p = n ρ u − ( n ρ − 1 ) q moves away from the minimum-redundancy mixture q \boldsymbol{q} q towards high-degree tasks (Remark C.2), and the nonnegativity constraint switches off the tasks that p ~ \widetilde{\boldsymbol{p}} p would make negative. Larger n ρ n\rho n ρ therefore means fewer active tasks, concentrated on the most representative ones; n ρ n\rho n ρ close to 1 means nearly uniform coverage. The KKT conditions make this precise: every active task has the same net utility ρ ( d + τ 1 ) [ i ] − ( S p ∗ ) [ i ] = ν \rho(\boldsymbol{d}+\tau\mathbf{1})_{[i]}-(S\boldsymbol{p}^*)_{[i]}=\nu ρ ( d + τ 1 ) [ i ] − ( S p ∗ ) [ i ] = ν (Section B.2), so a task is included exactly when its degree clears a threshold that rises with n ρ n\rho n ρ . Equivalently, the KKT fixed point is p ∗ = [ ( ρ d − S p ∗ ) / τ − θ 1 ] + \boldsymbol{p}^*=[(\rho\boldsymbol{d}-S\boldsymbol{p}^*)/\tau-\theta\mathbf{1}]_+ p ∗ = [( ρ d − S p ∗ ) / τ − θ 1 ] + : a thresholded, degree-driven allocation [?] corrected by the pairwise term S p ∗ S\boldsymbol{p}^* S p ∗ . Table 3 shows the resulting path: as n ρ n\rho n ρ grows from 1.85 to 618, the support shrinks from 302 to 6 tasks and the effective size from 289.8 to 2.4, while the effect of the pairwise term shrinks from TV 0.097 to 0.001.
The operating point ρ = 0.02424 \rho= 0.02424 ρ = 0.02424 . All experiments use ρ = 0.02424 \rho= 0.02424 ρ = 0.02424 (n ρ = 7.49 n\rho= 7.49 n ρ = 7.49 ; reported as 0.0242 in the main text), together with τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 . The value is a declared coverage choice, made before fine-tuning: it keeps two thirds of the pool active (206 of 309 tasks, effective size e H ( p ∗ ) = 179.6 e^H(\boldsymbol{p}^*) = 179.6 e H ( p ∗ ) = 179.6 ), so that the budget covers most of the pool’s breadth, while still excluding the tasks whose degree is lowest. The affinity matrix alone does not identify a unique ρ \rho ρ : intrinsic criteria, such as knees of the support-size or effective-size curves along the ρ \rho ρ path, disagree with one another by an order of magnitude. We therefore report the entire path (Table 3) and the behaviour of the mixture along it (Table 4). At this point the pairwise term is active but moderate: removing it moves 3.5% of the mass, and within its support p ∗ \boldsymbol{p}^* p ∗ stays within TV 0.011 of a degree-only allocation with the same support size (Spearman( p ∗ , d ) = 0.999 (\boldsymbol{p}^*,\boldsymbol{d}) = 0.999 ( p ∗ , d ) = 0.999 on the support). In other words, at n ρ = 7.49 n\rho= 7.49 n ρ = 7.49 , ρ \rho ρ mainly sets how many tasks receive weight, and the weights within that support follow task degree (Section E.2).
Solver and its verification
Algorithm. For τ > τ c \tau> \tau_c τ > τ c , (19) is a strictly convex quadratic program over Δ n \Delta_n Δ n , and we solve it exactly with Algorithm 1: accelerated projected gradient (FISTA; [5 ] ) on 1 2 p T S ~ p − ρ 1 T S ~ p \frac{1}{2}\boldsymbol{p}^{\mathsf{T}}\widetilde{S}\boldsymbol{p}-\rho\mathbf{1}^{\mathsf{T}}\widetilde{S}\boldsymbol{p} 2 1 p T S p − ρ 1 T S p (the objective divided by λ \lambda λ ), with gradient S ~ ( p − ρ 1 ) \widetilde{S}(\boldsymbol{p}-\rho\mathbf{1}) S ( p − ρ 1 ) , step 1 / L 1/L 1/ L with L = λ max ( S ~ ) L=\lambda_{\max}(\widetilde{S}) L = λ m a x ( S ) , the exact Euclidean projection onto Δ n \Delta_n Δ n by sorting ([DSSC08, Con16]), uniform initialisation, and the stopping rule ∥ p j + 1 − p j ∥ < ϵ \lVert\boldsymbol{p}_{j+1}-\boldsymbol{p}_j\rVert< \epsilon ∥ p j + 1 − p j ∥ < ϵ . Plain
From the mixture to a training set
Table 3. The ρ \rho ρ path at τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 . ρ \rho ρ alone controls breadth. “Interaction effect” is the TV between p ∗ \mathbf{p}^* p ∗ and the solution of the same problem with S \mathbf{S} S removed from the quadratic term, Π Δ n ( ρ ( d + τ 1 ) / τ ) \Pi_{\Delta_n}(\rho(\mathbf{d}+\tau\mathbf{1})/\tau) Π Δ n ( ρ ( d + τ 1 ) / τ ) ; it grows as n ρ n\rho n ρ decreases. The operating point is in bold.
projected gradient with step η ≤ 1 / L \eta\le1/L η ≤ 1/ L converges at rate O ( 1 / t ) O(1/t) O ( 1/ t ) , FISTA at O ( 1 / t 2 ) O(1/t^2) O ( 1/ t 2 ) , and both converge linearly once τ > τ c \tau> \tau_c τ > τ c by strong convexity on the simplex. Each iteration costs one matrix–vector product and one O ( n log n ) O(n\log n) O ( n log n ) projection.
Why not the closed form. The equality-constrained stationary point p ~ \tilde{\mathbf{p}} p ~ (Corollary 2, (13) ) is the minimiser only when p ~ ≥ 0 \tilde{\mathbf{p}} \ge0 p ~ ≥ 0 . At our operating point 66 of its 309 entries are negative, so it is not feasible, and renormalising its positive part does not give a minimiser of (19) (it violates the KKT conditions of Section B.2). We therefore always solve the constrained problem exactly.
Verification of the deployed mixture. With ρ = 0.02424 \rho= 0.02424 ρ = 0.02424 , τ = τ 0 + 10 − 3 \tau= \tau_0 + 10^{-3} τ = τ 0 + 1 0 − 3 and ϵ = 10 − 14 \epsilon= 10^{-14} ϵ = 1 0 − 14 , Algorithm 1 converges in 38 iterations, in under a second on a CPU. The solution has 206 active tasks; the gradient is constant on the support to 3 × 10 − 14 3 \times10^{-14} 3 × 1 0 − 14 and exceeds it by at least 4.7 × 10 − 3 4.7 \times10^{-3} 4.7 × 1 0 − 3 on every inactive task, so the full KKT conditions hold, including complementary slackness, and the solution is the unique minimiser. Re-running the algorithm reproduces the mixture file used for fine-tuning to TV 5 × 10 − 16 5 \times10^{-16} 5 × 1 0 − 16 ; a looser tolerance ϵ = 10 − 12 \epsilon= 10^{-12} ϵ = 1 0 − 12 changes it by TV 2.5 × 10 − 13 2.5 \times10^{-13} 2.5 × 1 0 − 13 . Rounding ρ \rho ρ to 0.0242 would change it by TV 3.9 × 10 − 4 3.9 \times10^{-4} 3.9 × 1 0 − 4 (still 206 tasks), which is why we report the unrounded value here.
From the mixture to a training set
Given p ∗ p^* p ∗ and a budget B \mathcal{B} B , per-task counts are obtained as follows: (i) Draw 5 independent samples k ( r ) ∼ Mult ( B , p ∗ ) k^{(r)} \sim\operatorname{Mult}(\mathcal{B}, p^*) k ( r ) ∼ Mult ( B , p ∗ ) with seeds 42, …, 46 and average them, which reduces the sampling noise of a single draw while keeping E [ k i ] = B p i ∗ \mathbb{E}[k_i] = \mathcal{B}p_i^* E [ k i ] = B p i ∗ . (ii) Round the average to integers summing exactly to B \mathcal{B} B by the largest-remainder method. (iii) If a count exceeds its task’s size, cap it at ∣ D i ∣ |\mathcal{D}_i| ∣ D i ∣ and redistribute the deficit proportionally among the tasks with headroom, until no task is over capacity. At B = 25 K \mathcal{B} = 25\mathrm{K} B = 25 K no task is capped; at B = 50 K \mathcal{B} = 50\mathrm{K} B = 50 K one task is (TULU_HARDCODED, 240 examples, expected 289). (iv) Sample k i k_i k i examples from task T i T_i T i uniformly without replacement, with a per-task seed derived from the base seed and the task index. Tasks outside the support of p ∗ p^* p ∗ contribute nothing; every active task has an expected count of at least one at both budgets.
Experimental Details
Computing the affinity matrix
One affinity, reused for all models. S S S is computed once, from Qwen2-7B single-task models, and the resulting mixture is reused unchanged for all three base models (Qwen2-7B, Llama-2-7B and Qwen3.5-9B). We do not recompute S S S per model, so the Llama-2-7B and Qwen3.5-9B results also test whether a mixture derived on one model transfers to other model families and sizes.
Single-task models. For each of the 309 tasks we train a LoRA adapter on Qwen2-7B (rank 8, α = 32 \alpha= 32 α = 32 , dropout 0.1, on the query, key, value and output projections) for one epoch on the task’s full training split, with learning rate 2 × 10 − 5 2 \times10^{-5} 2 × 1 0 − 5 , cosine schedule, weight decay 0.01, bf16, per-device batch 16 on 4 GPUs, maximum sequence length 4096 and seed 23. Task sizes range from 240 to 363,846 examples (median 10,000, 6.32M in total). Each adapter is about 18 MB.
Cross-evaluation. Each adapter is merged into the base model and scores every task on m = min ( 2048 , ∣ D j ∣ ) m = \min(2048, |\mathcal{D}_j|) m = min ( 2048 , ∣ D j ∣ ) held-out examples (never used to train any adapter), drawn with a fixed seed; 277 of the 309 tasks exceed the cap. Scoring uses maximum length 512 and computes the mean per-token log-probability of the response, averaged over examples. This gives the n × n n \times n n × n log-likelihood matrix L L L , and S = 1 2 [ ( L − 1 diag ( L ) ⊤ ) + ( ⋅ ) ⊤ ] S = \frac{1}{2}[(L - \mathbf{1}\operatorname{diag}(L)^\top) + (\cdot)^\top] S = 2 1 [( L − 1 diag ( L ) ⊤ ) + ( ⋅ ) ⊤ ] with zero diagonal (Equation (5) ). Because the scoring examples are held out, the diagonal L j j L_{jj} L j j measures generalisation of the own-task model rather than memorisation, and is not inflated relative to the cross terms.
Cost and scaling. The procedure needs n n n LoRA runs (cost linear in the pool size, ∑ i ∣ D i ∣ \sum_i |\mathcal{D}_i| ∑ i ∣ D i ∣ ) and n 2 = 95,481 n^2 = 95{,}481 n 2 = 95 , 481 model–task evaluations of at most m m m examples each (cost O ( n 2 m ) O(n^2m) O ( n 2 m ) ), which dominates as n n n grows but parallelises trivially across adapters. Empirically, computing the complete PMI matrix for Qwen2-7B on 8-H100 GPUs required approximately 16 hours of wall-clock time, corresponding to about 128 H100-GPU-hours in total, or 0.41 GPU-hours per adapter row.
The cost is paid once per task pool. Adding a task requires one LoRA run and 2 n 2n 2 n new evaluations, without recomputing existing entries. Storage is negligible: the symmetric matrix has n ( n − 1 ) / 2 = 47,586 n(n - 1)/2 = 47{,}586 n ( n − 1 ) /2 = 47 , 586 entries (≈ 0.18 \approx0.18 ≈ 0.18 MB in float32).
Final fine-tuning on the mixture
The reported models are fine-tuned on training sets sampled from p ∗ p^* p ∗ (Section C.6) at budgets of 25K and 50K examples, for one epoch, with AdamW (learning rate 2 × 10 − 5 2 \times10^{-5} 2 × 1 0 − 5 , weight decay 0.01), bf16, DDP and gradient checkpointing, and maximum sequence length 2048. To reduce run-to-run variability, for each base model, budget, and method we repeat fine-tuning three times on the same mixture with different seeds (affecting data order, dropout, and other stochastic components) and report the mean; when shown, the ± \pm ± subscript denotes the standard deviation across these three runs. All runs use LoRA with rank r = 8 r = 8 r = 8 , α = 32 \alpha= 32 α = 32 , and dropout 0.1. For Qwen2-7B and Llama-2-7B, LoRA is applied to the attention projections q_proj, k_proj, v_proj, and o_proj. For Qwen3.5-9B, we additionally adapt in_proj_qkv, in_proj_z, in_proj_b, in_proj_a, out_proj, and the MLP projections gate_proj, up_proj, and down_proj. All other optimization and training hyperparameters are held fixed across models and methods. Every method within a table, including all baselines, is trained with the same configuration on the same base model, so differences reflect only the training data.
Baselines
All baselines draw from the same 309-task pool and budget B \mathcal{B} B . Uniform, EPM and Random are defined in the main text (Items 1 to 3) and use the same capping and within-task sampling as Section C.6. SMART [35 ] allocates the budget across tasks with its submodular objective and selects non-redundant examples within each task. LESS [49 ] uses a LoRA warm-up on a random 5% of the pool (seed 3), Adam-preconditioned training gradients projected to 4,096 dimensions, and standard SGD gradients on validation examples to form each benchmark’s average target gradient. It selects the top 0.25% (25K) or 0.5% (50K) examples by cosine similarity between training and validation gradients, then trains one checkpoint per benchmark.
Evaluation
We evaluate with the EleutherAI lm-evaluation-harness [37 ] on the six Open LLM Leaderboard benchmarks: BBH and MuSR (reasoning), GPQA and MMLU-Pro (knowledge), MATH-hard (Level-5 MATH) and IFEval (instruction following; we reported instruction-level-loose accuracy), using the leaderboard task definitions and few-shot settings. All numbers are averages over the three fine-tuning repeats described above.
Comparison with LESS: Lack of Cross-Model Amortization
LESS [49 ] requires computing and storing per-example LoRA gradients for the entire candidate pool at each warm-up checkpoint, making gradient construction scale linearly with the pool size and number of checkpoints. This gradient-storage stage alone required approximately 320 hours of wall-clock time on 4 H100 GPUs. Importantly, these gradients are model-specific; gradients computed using Llama2 or Qwen2 cannot be reused directly when switching to Qwen3.5, since both the parameterization and resulting optimization geometry change. Thus, LESS requires repeating the warm-up and gradient-construction stages for new models. The datastore also incurs substantial storage overhead, since per-example gradient representations must be materialized and retained across warm-up checkpoints. The gradient construction for Qwen3.5-9B model required roughly 460 hours on 4 H100s under the same data and sequence-length . This model-dependent recomputation represents a substantial disadvantage relative to a model-agnostic TaskMixPGM method, for which the selection artifact can be reused across model families without incurring this cost again.
Additional Results and Analysis
Structure of the learned mixture
Sparse, broad selection. The deployed mixture assigns positive weight to 206 of the 309 tasks (effective size 179.6; entropy 5.19 against the uniform maximum ln 309 = 5.73 \ln309 = 5.73 ln 309 = 5.73 ). The sparsity is not imposed by any cardinality constraint: it follows from the KKT threshold of Section C.4, which excludes the 103 tasks with the lowest degree.
Which tasks are kept. Reordering S S S by learned weight (Figure 10 ) shows the structure the optimiser exploits. The 206 active tasks form a block of weak mutual affinity (S i j S_{ij} S ij near 0), while the 103 inactive tasks have strongly negative affinity to almost every task, including each other: they are specialised tasks whose models transfer poorly and whose data other tasks’ models predict poorly. The highest-weighted tasks, the “attractors”, are broad reading-comprehension and QA prompts from T0 (RACE, QuAIL, Social IQa, WebQuestions, WikiQA) and Flan (linear-algebra math, STS-B, QuAC, Newsroom); their weight ranks follow their degree ranks almost exactly (the top 15 by weight are the top 15 by degree; Figure 5 ).
Figure 5. The 15 highest-weighted tasks, coloured by collection, with each task’s rank by degree S [ i ] S[i] S [ i ] . The full structure of the mixture, including the affinity matrix reordered by weight, is analysed in Section E.1.
Figure 10. S S S reordered by learned weight: the 206 active tasks in decreasing p [ i ] ∗ p^*_{[i]} p [ i ] ∗ , followed by the 103 inactive tasks (average-linkage clustering). Side strips show the source collection and p [ i ] ∗ p^*_{[i]} p [ i ] ∗ . Colour scale clipped at − 2 -2 − 2 .
Collection-level allocation. T0 receives 0.649 of the mass (135 of 193 tasks active), Flan 2021 0.221 (40/63), Tulu 0.066 (15/18), CoT 0.059 (14/18) and SuperGLUE 0.006 (2/17). SuperGLUE prompts are the least transferable in this pool, a bias of degree-driven weighting noted in the limitations.
Role of the pairwise term
We compare p ∗ p^* p ∗ with two variants that keep only the unary (degree) information. Pairwise-removed replaces S ~ \tilde{S} S ~ by τ I \tau I τ I in the quadratic term, giving Π Δ n ( ρ ( d + τ 1 ) / τ ) \Pi_{\Delta_n}\bigl(\rho(d+\tau\mathbf{1})/\tau\bigr) Π Δ n ( ρ ( d + τ 1 ) / τ ) . Degree, support-matched is Π Δ n ( a d ) \Pi_{\Delta_n}(a d) Π Δ n ( a d ) with the scale a a a chosen so its support has the same size as p ∗ p^* p ∗ . At every ρ \rho ρ we tested, p ∗ p^* p ∗ lies within TV 0.011 of the support-matched degree allocation, except at $n_\rho = 618 where only 6 tasks are active (Table 4 ). The pairwise term mainly determines how many tasks are active, through ρ \rho ρ , and changes the weights within that support only slightly. At the operating point, removing it moves 3.5% of the mass and the support-matched degree rule moves 1.1%.
Incremental composition
Figure 4 adds tasks one at a time, in greedy order and in five random orders, and re-solves on the growing support, measuring both the task affinity of the main text and its renormalised version T V ‾ k \overline{\mathrm{TV}}_k TV k . With the shift, the existing mixture is almost unaffected by each new task: T V ‾ k \overline{\mathrm{TV}}_k TV k has median 0.0026 for k < 10 k < 10 k < 10 and 0.0010 for k ≥ 150 k \ge150 k ≥ 150 , and never exceeds 0.007. The support grows steadily to the 206 tasks of p ∗ ( τ 0 ) p^*(\tau_0) p ∗ ( τ 0 ) , and the final mixture equals p ∗ ( τ 0 ) p^*(\tau_0) p ∗ ( τ 0 ) (TV < 10 − 13 < 10^{-13} < 1 0 − 13 ) for every order. Without the shift every intermediate mixture is a single task: in random orders the mixture stays the same at 98% of steps, and at the remaining 4–9 steps per order all mass jumps to the newly added task. The final task then depends on the order; in 3 of 5 orders it is not the globally best task.
Larger budget on Llama-2-7B
Table 5 extends the Llama-2-7B comparison to a 100K budget.
Table 5. Llama-2-7b: Instruction-tuning performance on Leaderboard subsets using batch size 8. Scores are reported as mean ± \pm ± std. over three fine-tuning repeats on the same mixture with different seeds).
The PMI mixture is strongest on BBH, MMLU-Pro and MuSR at every budget, reaching 0.4201 on BBH and 0.4665 on MuSR at 100K, and improves over Uniform and EPM on BBH by up to 7 points. On several benchmarks the PMI mixture at 50K matches or exceeds the heuristic mixtures at 100K (e.g. MuSR and Math), which indicates that the selected tasks carry more useful signal per example. The heuristic baselines do not improve consistently with budget: Random and EPM gain on some benchmarks while losing on others as the budget grows, because extra examples drawn without regard to task structure are not necessarily useful.
Comparing Notions of Task Similarity
Similarity across Task Vectors via Linearized finetuning
Large-scale pretrained language models (PLMs) such as GPT-2 are widely adapted to downstream tasks via full-model fine-tuning. However, multi-task or per-task retraining remains computationally burdensome. Task arithmetic ([32 ] ) introduces a simple yet effective approach: given a pretrained checkpoint initialization θ 0 \theta_0 θ 0 and task-specific fine-tuned weights θ t ∗ \theta_t^* θ t ∗ , the task vector is defined as:
τ t : = θ t ∗ − θ 0 \tau_t := \theta_t^* - \theta_0 τ t := θ t ∗ − θ 0
These vectors enable model editing via linear composition:
While effective, the underlying mechanisms behind this arithmetic remain poorly understood. Linearized Fine-Tuning: [32 ] posit that tangent-space fine-tuning disentangles task behaviors more effectively by constraining updates to the local linear approximation of the model. Let f ( x ; θ ) f(x; \theta) f ( x ; θ ) denote a PLM with parameters θ ∈ R m \theta\in\mathbb{R}^{m} θ ∈ R m , the corresponding nonlinear task vector is given by τ t n l : = θ t ∗ − θ 0 \tau_{t}^{\mathrm{nl}} := \theta_{t}^{*} - \theta_{0} τ t nl := θ t ∗ − θ 0 .
In contrast, linearized fine-tuning restricts optimization to the first-order Taylor expansion:
f l i n ( x ; θ ) : = f ( x ; θ 0 ) + ∇ θ f ( x ; θ 0 ) ⊤ ( θ − θ 0 ) f_{\mathrm{lin}}(x; \theta) := f(x; \theta_{0}) + \nabla_{\theta}f(x; \theta_{0})^{\top}(\theta- \theta_{0}) f lin ( x ; θ ) := f ( x ; θ 0 ) + ∇ θ f ( x ; θ 0 ) ⊤ ( θ − θ 0 )
This surrogate is optimized using Jacobian-vector products (JVP), yielding a linearized task vector:
τ t l i n : = θ t l i n ∗ − θ 0 \tau_{t}^{\mathrm{lin}} := \theta_{t}^{\mathrm{lin}*} - \theta_{0} τ t lin := θ t lin ∗ − θ 0
Task vectors are generally useful as they can enable model editing as well provide a well defined representation of the finetuning task at hand, dependent on the model parameters. Ideally, the goal would be to select multiple linearly independent task vectors such that they represent generalizably well across a range of IFT datasets and does generalizably well across different benchmark datasets. The algorithm is presented as Algorithm 1 in Section F.2.
Similarity Structure of Task Embeddings Directly computing any similarity metric over m ∼ 10 6 m \sim10^{6} m ∼ 1 0 6 to 10 9 10^{9} 1 0 9 parameters, is computationally expensive. Thus, we first isolate the most informative layer (chosen via task-vector analysis using layer-wise subsetting and then project its high-dimensional slice task vector τ ∈ R m \tau\in\mathbb{R}^{m} τ ∈ R m to a much lower-dimensional vector τ ~ = R τ ∈ R k \tilde{\tau} = R\tau\in\mathbb{R}^{k} τ ~ = R τ ∈ R k using a Gaussian random matrix R ∈ R k × m R \in\mathbb{R}^{k \times m} R ∈ R k × m with k ≪ m k \ll m k ≪ m . This projection technique is known to preserve similarity distances in expectation, providing a reliable and efficient approximation for comparing vector directions in the reduced space.
Cosine Similarity across Task Vectors: To analyze inter-task relationships, we examine the cosine similarity between task vectors:
sim ( τ A , τ B ) : = τ A ⊤ τ B ∥ τ A ∥ 2 ⋅ ∥ τ B ∥ 2 ∈ [ − 1 , 1 ] \operatorname{sim}(\tau_A, \tau_B) := \frac{\tau_A^{\top}\tau_B}{\lVert\tau_A\rVert_2 \cdot\lVert\tau_B\rVert_2} \in[-1, 1] sim ( τ A , τ B ) := ∥ τ A ∥ 2 ⋅ ∥ τ B ∥ 2 τ A ⊤ τ B ∈ [ − 1 , 1 ]
This metric probes the angular alignment between task-specific directions in parameter space. High similarity indicates shared representational updates; near-orthogonality suggests disentangled task pathways.
Analyzing Task Vector Relationships via Cosine Similarity and PMI: While Cosine Similarity is a commonly used metric for comparing vector representations, it falls short in capturing nuanced differences in model behavior when applied to classification probability distributions. Cosine only measures the angular similarity between two vectors and is therefore invariant to vector magnitude. Hence, two models assigning vastly different probabilities but in the same proportional direction can still yield a high cosine score, misleadingly implying strong similarity. This limitation becomes evident in our experimental heatmap (Figure 11a ), where task relationships are not clearly differentiated as many unrelated tasks appear spuriously similar due to their shared vector directionality. Moreover, cosine similarity does not adequately account for uncertainty or confidence in model outputs.
To address these issues, we used Pointwise Mutual Information (PMI), which offers better theoretical grounding and practical discriminability. As shown in Figure 11b , PMI captures directional alignment of model predictions with respect to task-specific specialization and yields a more interpretable heatmap where related tasks cluster more meaningfully and task-specific behaviors are more distinctly captured. Concretely, the cosine heatmap appears overly uniform and thus masking important task groupings; whereas the PMI map exposes clear blocks of high intra-group similarity and low inter-group coupling. These results confirm that, for fine-grained task-similarity assessment in large models, information-theoretic measures substantially outperform simple angular alignment.
Figure 11 visualizes the effects (on SGLUE tasks), comparing cosine and PMI heatmaps to illustrate their differing sensitivity to inter-task relationships.
(a) (a) Cosine Similarity
(b) (b) PMI
Figure 11. Comparison of task similarity metrics using cosine similarity and PMI-based heatmaps. Cosine scores are generally low and fail to distinguish task structure. PMI highlights asymmetric task alignment and reveals clearer task groupings across models.
Algorithms for computing PMI
Algorithm 1 performs fine-tuning by linearizing the model around its pretrained parameters. Instead of recomputing the full forward pass, it uses a Jacobian-vector product (JVP) to approximate the effect of parameter updates, allowing faster gradient-based updates in the “tangent space” of the original model.
Algorithm 1: Linearized (Tangent-Space) Fine-Tuning
Require: Pretrained weights θ 0 \theta_0 θ 0 , dataset D t \mathcal{D}_t D t
Initialize θ ← θ 0 \theta\leftarrow\theta_0 θ ← θ 0
while not converged do
Sample mini-batch ( x , y ) ∼ D t (x,y) \sim\mathcal{D}_t ( x , y ) ∼ D t
Compute base output o 0 = f ( x ; θ 0 ) o_0 = f(x;\theta_0) o 0 = f ( x ; θ 0 )
Compute JVP: g = JVP f ( ⋅ ; θ 0 ) , θ − θ 0 ; x g = \operatorname{JVP}_f(\cdot;\theta_0),\theta-\theta_0;x g = JVP f ( ⋅ ; θ 0 ) , θ − θ 0 ; x
o ^ = o 0 + g \hat{o} = o_0 + g o ^ = o 0 + g
θ ← θ − η ∇ θ ℓ ( o ^ , y ) \theta\leftarrow\theta- \eta\nabla_\theta\ell(\hat{o},y) θ ← θ − η ∇ θ ℓ ( o ^ , y )
end while
return θ t l i n ∗ \theta_t^{\mathrm{lin}*} θ t lin ∗
Algorithm 2 quantifies how similarly two models M A M_A M A and M B M_B M B score the same labeled examples, using a pointwise mutual information (PMI)–inspired score. By averaging the log-ratio of predicted probabilities on each other’s held-out data, it produces a symmetric similarity score S A B S_{AB} S A B .
Table 2 (PDF p. 35).
Potential Data Contamination
A fair evaluation requires that the fine-tuning mixture does not contain the benchmark questions it is later evaluated on. This section examines that risk for every source collection in our pool and reports an instance-level overlap audit.
We distinguish task- or capability-level relatedness from instance-level evaluation leakage . The former is expected in general-purpose instruction tuning: for example, our pool contains AQuA and StrategyQA, which exercise multi-step reasoning skills also required by BBH. Such relatedness does not imply that BBH evaluation questions or answers were observed during fine-tuning. We further describe documented safeguards for upstream sources.
MMLU and BBH held-out. The Flan Collection defines MMLU and BBH as held-out tasks that are not included in Flan-2022 fine-tuning [25 Sec. 2.2] . Its Appendix B [25 Appendix B] further states that MMLU tasks were removed from the Super-Natural Instructions component to preserve this separation. The Scaling Flan paper [8 ] further reports removing 44 tasks related to MMLU and explicitly states that MMLU and BBH are held-out and absent from its fine-tuning data.
Composition of the CoT mixture. Scaling Flan lists the nine CoT training datasets as AQuA, CREAK, ECQA, ESNLI, GSM8K, QASC, QED, SenseMaking, and StrategyQA; MATH and BBH are not listed as CoT training sources [8 A.4] .
Chronology of legacy sources. The official T0 release dates to October 2021, while GLUE and SuperGLUE date to 2018 and 2019, respectively. By comparison, GPQA (Nov. 2023), IFEval (Nov. 2023), MuSR (Oct. 2023), and MMLU-Pro (Jun. 2024) post-date these sources. Therefore, as a chronological inference, the newly authored GPQA questions, newly constructed IFEval prompts, and newly generated MuSR narratives could not have appeared in the frozen official T0, GLUE/SuperGLUE, or earlier CoT releases.
Tulu V3 decontamination. For the later Tulu V3 component, we used the official decontaminated release. The Tulu V3 technical report states that a training dataset is excluded when its overlap exceeds 2% of the Tulu evaluation suite, and the official Open-Instruct implementation supports full-text, token n n n -gram, and embedding-based matching with removal of matched training instances. We treat this as meaningful risk mitigation rather than proof of zero contamination, because the implementation notes that retrieval limits may prevent removal of every possible match.
Instance-level overlap audit. We conducted an instance-level overlap audit between the available TaskMixPGM source pool and the final evaluation benchmarks. The audit covers 6,072,160 training and validation examples from 309 source tasks. For every evaluation example, we applied: (i) normalized exact matching (full-text equality after lowercasing and removing punctuation and prompt wrappers), (ii) token overlap using a 13-gram criterion (as in prior GPT-3 contamination analyses), and (iii) semantic matching to detect paraphrases and translated/reformatted copies (cf. Yang et al., 2023).
We audited the BBH leaderboard subset, GPQA leaderboard subsets, IFEval, MATH-hard level-5, MMLU-Pro, and MuSR. Table 6 summarizes the first-stage results.
Table 6. First-stage overlap audit between the TaskMixPGM source pool (309 tasks) and evaluation benchmarks. “13-gram candidates” are lexical hits requiring adjudication; a shared 13-gram may arise from repeated templates, mathematical expressions, or standard instructional language and does not by itself establish leakage.
The audit found no normalized exact duplicates in any evaluated benchmark. The 13-gram overlap rates are below 1% for five of the six benchmarks. MATH-hard has a higher candidate rate (20.77%); these cases require additional adjudication, so we do not treat every lexical hit as confirmed contamination.
Additional Related Work
Mixture optimisation and task affinity. Domain-reweighting methods choose mixture proportions with proxy models: DoReMi [50 ] reweights domains by minimax excess loss of a small proxy, and RegMix [29 ] regresses downstream loss on proxy-trained mixtures. Both require training runs per candidate mixture and target pretraining domains. Skill-It [10 ] estimates a graph of skill dependencies from training dynamics and uses it to order and mix data, the closest conceptual neighbour of our affinity graph. Task affinity grouping [16 ] likewise measures inter-task transfer from behaviour (lookahead loss changes), but uses it to partition tasks for multi-task training rather than to weight them. Our objective is a quadratic quality–diversity trade-off of the kind detrimental point processes formalise [23 ] . Unlike a DPP, it returns continuous proportions on the simplex, has a closed-form convexity threshold τ c \tau_c τ c , and needs no proxy training beyond the single-task adapters.
Broader Impact
TaskMixPGM changes which data a model is fine-tuned on, not how the model is trained, so its effects follow from the mixtures it produces.
Cheaper and more transparent mixture design. Choosing an SFT mixture is usually done by hand or by expensive search over training runs. TaskMixPGM computes a mixture once, from single-task adapters and without benchmark data, and reuses it for every budget and base model. Because the mixture follows from an explicit affinity matrix, practitioners can inspect why a task received weight, which tasks it is redundant with, and how the allocation changes with the trade-off parameter.
Auditing training pools. The affinity graph exposes clusters of near-duplicate tasks and tasks that the pool covers poorly. This can help curators find redundancy and gaps in large instruction collections before training.
Limitations and risks. TaskMixPGM optimizes over the task pool it is given; it cannot add capabilities that the pool lacks, and it inherits the biases and quality issues of the underlying datasets. By favouring representative tasks it may also down-weight small or specialized tasks, including safety- or language-specific data, unless these are protected explicitly. We recommend inspecting the resulting mixture for such omissions before deployment.
Code
An anonymized version of our code is available at https://anonymous.4open.science/r/taskpgm_ais-B555 .
Dataset and Task Names
This section lists all datasets/tasks in our pool, along with their short task identifiers and one-line descriptions.
Table 7. Dataset and task names.