{"id":"3865d94c-5647-4f05-aaa2-b14760d4a201","arxiv_id":"2504.13835","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"MIG greedily selects instruction-tuning data by maximizing a concave information measure over a label graph, and with 5% of Tulu3 data it matches or exceeds full-data SFT performance.","lead":"This paper proposes MIG, a method that chooses instruction-tuning examples for AI assistants by maximizing information gain over a graph of task labels. It reports that models trained on only 5% of the Tulu3 dataset selected this way match or beat models trained on the full dataset.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 is not executable as written: Eq. (10) drops the transpose of the non-symmetric propagation matrix A, and Φ'(0)=∞ for the chosen Φ(x)=x^0.8, leaving the first gradients undefined.","rationale":"The reader's weakest assumption is the unanalyzed gap between the exact submodular gain and the gradient approximation. I agree that gap matters, but the paper has a more concrete problem in the same place. From Eq. (8), the first-order marginal score should be (A^T Φ'(z))·e_d; Eq. (10) and Alg. 1 use AΦ'(z). Since Eq. (6) defines a row-dependent normalization, A is not generally symmetric, so the published rule is not even the correct first-order approximation. Additionally, with the chosen Φ(x)=x^0.8, Φ'(0) is infinite; with D_S empty the score vector is undefined, so Algorithm 1 cannot be run without an unstated stabilization. This does not prove the empirical results are wrong—the authors may have implemented something sensible—but it means the method that produced Tables 1–2 is not specified by the paper, and the theoretical guarantee in Appx. C does not cover the reported procedure. The empirical concerns about single-seed runs and eval-set grid search remain valid; a reader should ask for code and a corrected derivation before treating the 5%-of-Tulu3 claim as settled. That is consistent with the CONDITIONAL verdict, so I leave the verdict unchanged.","tokens_in":17787,"tokens_out":16352,"duration_ms":165890,"concrete_test":"Re-implement Eq. (9) and Eq. (10) on a random 1K subset of Tulu3 (same A from Eq. 6, Φ(x)=x^0.8, budget N=100) and compare the two selected sets. If the first score vector G is non-finite, or if the sets overlap by less than ~90%, the published algorithm is not the one covered by the submodularity argument, and the reported experiments need to be re-attributed to the actual implementation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"From Eq. (8), E(D)=Φ(AΣ_i s_i v_i). For z=AΣ_{i∈S}s_i v_i, the exact marginal gain of adding d (with e_d=s_d v_d) is Σ_k[φ(z_k+(Ae_d)_k)-φ(z_k)], whose first-order approximation is (A^T Φ'(z))·e_d. Eq. (10) and Algorithm 1 line 4 instead set G=AΦ'(z). The propagation matrix A defined in Eq. (6) is not symmetric in general: the denominator depends on p through w_p and the degree term Σ_{k≠p}w_pk, so A^T≠A. Unless an undocumented symmetrization is applied, the score G·e_d is not the first-order marginal gain, breaking the claimed connection between Algorithm 1 and the submodular greedy guarantee of Appx. C before any approximation error is considered. Second, the chosen Φ(x)=x^0.8 has Φ'(0)=∞. At the first iteration D_S=∅, so z=0 and G is a vector of infinities; the argmax in Eq. (11) is undefined, and any sample touching an untouched label receives an infinite score. No epsilon or stabilization is stated. The paper therefore does not specify the selection rule that actually produced Tables 1–2: the theoretical objective, the published algorithm, and the empirical procedure are not demonstrably the same. The empirical claims may survive a corrected implementation, but as written the central claim is not reproducible from the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MIG, an automatic data-selection method for instruction tuning. The method annotates each data point with a set of labels and a quality score, builds a weighted label graph, and defines a set function E(D) = Φ(A Σ_{i∈D} s_i v_i) that aggregates propagated label information through a concave, monotonically increasing elementwise function. The paper proves that E is submodular when the elementwise function is concave and non-decreasing, and then presents a greedy sampling algorithm that approximates the marginal information gain by a first-order gradient expression. Experiments on Tulu3, Openhermes2.5, and Xsota pools with Llama3.1-8B, Mistral-7B-v0.3, and Qwen2.5-7B report consistent improvements over baselines, including the headline result that 5% of Tulu3 data selected by MIG matches or exceeds the official full-data SFT model on human-preference benchmarks.","tokens_in":18092,"tokens_out":5569,"duration_ms":52673,"significance":"If correct, MIG would provide a principled and computationally efficient method for instruction-data selection, combining a submodular objective with a graph-based semantic model and a roughly 100-fold speedup over embedding-based alternatives. The submodularity proof in Appendix C is mathematically sound for the stated conditions, and the experimental scope is broad, spanning three data pools, three base models, and nine evaluation benchmarks. However, the paper's central methodological claims are compromised by serious gaps between the theory, the written algorithm, and the actual implementation: the gradient update in Eq. (10) is not the first-order marginal gain unless the propagation matrix is symmetric, the chosen φ(x)=x^{0.8} has an undefined derivative at the initial empty set, and no approximation error analysis connects the implemented gradient step to the (1-1/e) greedy guarantee. The reported empirical gains are also partly fitted because the key hyperparameters are tuned on the same evaluation benchmarks used for the main comparison. The underlying idea is promising, but the manuscript as written does not specify a reproducible selection rule.","major_comments":[{"comment":"The score G·e_d used in the algorithm is not the first-order approximation of the exact marginal gain in Eq. (9). For z = A Σ_{i∈D_S} e_i, the true first-order gain of adding d is e_d^T A^T Φ'(z), whereas Algorithm 1 computes Φ'(z)^T A^T e_d by taking G = AΦ'(z) and then G·e_d. Since the propagation matrix A defined in Eq. (6) is not symmetric (the denominator is indexed by the source label p), these two quantities differ. Consequently, the greedy algorithm whose submodularity guarantee is proved in Appendix C is not the algorithm that is executed. The authors should either correct the transpose, restrict A to be symmetric, or prove that the two expressions produce the same ranking of candidates.","section":"§3.3, Eq. (10), Algorithm 1, Eq. (6)"},{"comment":"The chosen information score function φ(x) = x^{0.8} has φ'(0) = ∞. At the first iteration of Algorithm 1, D_S is empty, so z = 0 and the vector G in Eq. (10) is a vector of infinities; the argmax in Eq. (11) is therefore undefined, and any data point that touches any label receives an infinite score. The manuscript does not state an epsilon offset, an initialization step, or any stabilization of the derivative. The selection rule that actually produced Tables 1 and 2 is consequently not specified, making the central empirical claim non-reproducible from the paper as written.","section":"§4.3 and Appendix A.2"},{"comment":"The (1-1/e) approximation guarantee of Nemhauser et al. applies to a greedy algorithm that evaluates the exact marginal gain of a submodular function. Algorithm 1 replaces that exact gain with the gradient approximation of Eq. (10), and no bound is given on the error between the approximate score and the true marginal gain. The paper therefore invokes a theoretical guarantee that does not formally cover the implemented method. Please either run the exact greedy algorithm (which is feasible with the graph-based objective), derive an approximation guarantee for the gradient-based selection, or present the gradient step explicitly as a heuristic without claiming the submodularity guarantee.","section":"Appendix C.2"},{"comment":"The hyperparameters that define MIG (sample budget, training epochs, φ exponent, propagation weight α, label set size, and edge threshold T) are selected by grid search on the same Tulu3 evaluation benchmarks that are later used to report the main results in Table 1. The Limitation paragraph acknowledges that the parameters depend on grid search, but the headline claim that MIG 'consistently outperforms' on Tulu3 is partly a fitted result. To support the generalization claim, the authors should either fix the parameters a priori across data pools, tune on a held-out validation set, or demonstrate that the reported improvements persist without per-pool tuning on the test benchmarks.","section":"§4.3, Table 3, Fig. 4-6, Limitation"}],"minor_comments":[{"comment":"The symbol σ is used in Eq. (3) without definition; from context it appears to be an indicator function, but this should be stated explicitly.","section":"§3.2, Eq. (3)"},{"comment":"The phrase 'upper-convex function' is inconsistent with the stated 'marginally diminishing information gain' and with the concavity assumed in Appendix C; the terminology should be corrected to 'concave' or 'with diminishing returns'.","section":"§3.2"},{"comment":"In the definition of the propagation weight a_{pq}, the quantity w_p is said to 'equal 1', which does not match its role as a normalizer in the denominator; the definition of w_p should be clarified.","section":"§3.2, Eq. (6)"},{"comment":"The notation E_k in Algorithm 1 is not defined and is inconsistent with e_i used in Eq. (10); please use consistent notation for the propagated information vectors.","section":"Algorithm 1, line 4"},{"comment":"The exponential candidate Φ(x) = 1 - e^{-αx} is introduced but no experimental results are reported for it; if it was evaluated, the results should be included, and if not, the equation should be removed or clearly marked as unused.","section":"§4.3, Eq. (12)"},{"comment":"The grid search table reports only the Avg score; please also report Avg_obj and Avg_sub, and ideally run multiple random seeds to provide a sense of variance, since the differences between some cells are small.","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"The core idea of modeling semantic diversity through a label graph with information propagation is interesting and the submodularity proof is correct for the stated objective. However, the discrepancy between the published algorithm and the claimed theoretical guarantee is serious: the transposition error in Eq. (10) and the undefined derivative at the first iteration mean that the selection rule is not specified, so the experimental tables cannot be independently reproduced. If the authors can provide corrected pseudocode, a precise implementation (including any epsilon or initialization), and an analysis of the approximation, the paper could become publishable. If they cannot, or if the empirical results were obtained with a materially different unpublished procedure, the paper should be rejected. I would also encourage the editor to require the authors to release code for the exact algorithm used."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The central idea here is genuinely new: model the instruction space as a label graph, propagate information along edges, and greedily maximize a concave information gain. That mechanism is a real departure from independent-label or embedding-distance methods, and the submodularity proof in Appx C is correct for the exact objective. The efficiency argument is plausible too: a graph over labels avoids the pairwise embedding costs of QDIT and DEITA. If the empirical claims hold, the 5% Tulu3 result is a useful data point.\n\nBut the paper has a load-bearing problem. The published Algorithm 1 is not executable as written. Eq. (10) defines G = A Φ'(A Σ e_i), but the correct first-order marginal gain for adding a data point is (A^T Φ'(z))·e_d. The propagation matrix A in Eq. (6) is not symmetric in general—the denominator depends on the row index—so the algorithm as written does not compute the gradient it claims. Worse, with Φ(x)=x^0.8, Φ'(0)=∞, so at the first iteration (D_S empty) the score vector G is all infinities and the argmax in Eq. (11) is undefined. No epsilon or stabilization is mentioned. The selection rule that produced Tables 1–2 is therefore not specified in the paper. The (1-1/e) guarantee from Appx C applies to the exact greedy marginal gain, not to the gradient approximation, and no error bound is given for that approximation. These aren't cosmetic typos; they break the link between the theory, the algorithm, and the reported results.\n\nThe empirical work is broad but not airtight. Hyperparameters (data size, epochs, graph parameters) are tuned on the same evaluation benchmarks used for the headline numbers—Table 3 is a grid search for the exact setup that produces the main results. All results are single runs, no variance estimates, and some margins are small (e.g., +0.41 on Openhermes2.5). The limitation section honestly admits the grid-search dependence, but that doesn't remove the circularity.\n\nBottom line: the formulation could become a real contribution, but this manuscript is not reproducible and the theoretical claims outrun what the algorithm actually implements. I would send it to peer review—the idea deserves referee attention—but with an expectation of major revision: correct the gradient (transpose, finite derivatives, an epsilon), release the code, add multi-seed runs, and move hyperparameter selection to a held-out split. As it stands, I wouldn't cite it, and I'd advise a student to read it for the label-graph idea but not to trust the reported gains.","headline":"Novel label-graph selection idea, but the published algorithm is not executable and the theory overclaims; worth peer review after a major fix.","tokens_in":18670,"tokens_out":4790,"would_cite":false,"duration_ms":44661,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that greedily maximizing information gain over a semantic label graph selects instruction-tuning data so well that 5% of the pool matches full-data fine-tuning.","keywords":["instruction tuning","data selection","submodular maximization","information gain","label graph","semantic diversity","data quality","LLM fine-tuning"],"falsifier":"Run MIG on a ~10K-record pool once with the exact marginal gain of Eq. (9) and once with the gradient approximation of Eq. (10); if the selected subsets differ appreciably in composition or downstream benchmark scores, then the implemented algorithm is not the submodular greedy method whose (1-1/e) guarantee is claimed.","tokens_in":17501,"feed_emoji":"🧠","tokens_out":8100,"duration_ms":65597,"temperature":0.7,"pith_summary":"The paper proposes a single quantitative measure for judging an instruction-tuning dataset: total information distributed over a semantic label graph, where each sample contributes its quality score to the labels it carries, and a concave function makes the measure submodular so greedy selection is near-optimal. The resulting algorithm, MIG, iteratively adds the sample with the largest approximate information gain, and the paper reports that this rule selects subsets that consistently outperform existing quality-and-diversity samplers across three data pools and three base models. Most strikingly, fine-tuning on 5% of the Tulu3 pool selected by MIG yields performance comparable to the official SFT model trained on the full 939K-record pool, with gains of +5.73% on AlpacaEval and +6.89% on Wildbench. If correct, this turns instruction-data curation from a heuristic art into a form of submodular optimization with a cheap, 100x-faster sampler.","feed_headline":"A 5% data subset matches full-data instruction tuning","feed_subtitle":"MIG greedily maximizes information gain over a label graph, doing in 0.45 GPU-hours what embedding methods take 80+ to do.","key_machinery":"The load-bearing object is the labeled semantic graph $G_L=(L,E_L)$ with weighted edges $w_{pq}$ from textual similarity (Eq. 3), the propagation matrix $A$ from Eq. (6)-(7), and the concave information score $\\phi$. The dataset measure $E(D)=\\Phi(A\\sum_{i\\in D} s_i v_i)$ is submodular (Appx. C), which licenses the greedy sampler of Alg. 1; the key computational step is the gradient approximation $G_k=A\\Phi'(A\\sum_{i\\in D_k} e_i)$ of the exact marginal gain, which avoids recomputing the whole objective and reduces selection cost to $O(NK)$ over labels rather than pairwise distances over the pool.","core_discovery":"The central claim is that the information content of an instruction-tuning dataset can be modeled as the aggregate of per-label information over a graph whose nodes are semantic labels and whose edges encode label similarity, with each data point $d_i$ depositing its quality score $s_i$ into its associated labels. Dataset information is $E(D)=\\Phi(A\\sum_{i\\in D} s_i v_i)$ where $v_i$ is the binary label vector, $A$ is a label-propagation matrix, and $\\Phi$ applies an increasing concave function $\\phi(x)=x^{0.8}$ elementwise, so that adding more data to an already information-rich label yields diminishing returns. This makes $E$ submodular, and MIG is the greedy algorithm that at each step selects the candidate with the largest marginal gain, computed via the gradient $G_k=A\\Phi'(A\\sum_{i\\in D_k} e_i)$. The paper's empirical claim is that the resulting subsets dominate prior selection methods on knowledge-based and human-preference benchmarks, and that a 5% Tulu3 sample matches or exceeds full-data SFT, demonstrating that a global semantic measure with a greedy optimizer can replace heuristic diversity filters and pairwise embedding distances.","pith_inferences":["Because the implementation replaces the exact submodular gain with a first-order gradient, the (1-1/e) guarantee formally applies to $E$ itself, not to the algorithm actually run; a direct comparison of exact-gain and gradient-gain selections on a small pool would tell how much of MIG's empirical edge comes from submodularity and how much from the DEITA quality scores that seed it.","The paper treats the label tagger and embedding model as fixed; since its own parameter sweeps show sensitivity to label granularity, an obvious extension is to co-train or adapt the label graph per data pool rather than grid-searching thresholds.","MIG's largest gains appear on human-preference benchmarks (Wildbench, AlpacaEval) rather than knowledge benchmarks, suggesting the same information-gain objective could serve as a data ordering or filtering step before RLHF, not only for SFT."],"forward_implications":["A 5% Tulu3 subset sampled by MIG (about 47K of 939K records) yields a Llama3.1-8B model whose nine-benchmark average matches the official full-data SFT, with human-preference scores up by +4.59%; dataset-size reduction of this magnitude changes the economics of post-training.","MIG's gains hold across Llama3.1-8B, Mistral-7B-v0.3, and Qwen2.5-7B and across Tulu3, Openhermes2.5, and Xsota, so the selection rule transfers without retuning per model family.","Sampling 50K records from Tulu3 takes about 0.45 GPU-hours with MIG versus 81-86 GPU-hours for DEITA and QDIT; removing the pairwise-distance bottleneck makes submodular selection practical at million-record scale.","The grid-search sweeps show unimodal performance ridges in label-set size and edge density, indicating that for each pool there is an optimal graph granularity, and that MIG's information-propagation weight $\\alpha=1.0$ outperforms no propagation by +2.76 average points."],"supporting_citations":[{"why":"supplies the DEITA quality scores used as MIG's default $s_i$, and represents the strongest quality-only baseline MIG must beat.","marker":"(Liu et al., 2024b)"},{"why":"provides the InsTagger and label set that define the nodes of MIG's label graph.","marker":"(Lu et al., 2024)"},{"why":"establishes the (1-1/e) approximation guarantee for greedy submodular maximization, the theoretical license for MIG's iterative selection.","marker":"(Nemhauser et al., 1978)"},{"why":"supplies the Tulu3 pool and the official full-data SFT baseline against which MIG's 5% subset is compared.","marker":"(Lambert et al., 2024)"},{"why":"provides QDIT, the second-best comparison method on Tulu3, which MIG outperforms by +2.20% average.","marker":"(Bukharin et al., 2024)"},{"why":"supplies the IFD baseline and the self-guided quality scores that MIG's information measure generalizes.","marker":"(Li et al., 2024b)"}],"fun_headline_variants":["5% of data, full-data results via info gain maximization","MIG: 5% subset matches full instruction tuning","Greedy info gain: 5% data beats full tuning","0.45 GPU-hrs to match full-data SFT","5% Tulu3 data rivals full fine-tuning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The implemented greedy sampler assumes that the first-order gradient in Eq. (10) ranks candidate data points the same way the exact submodular marginal gain in Eq. (9) would, and the paper provides no error bound for that approximation.","fun_headline_variants_meta":{"raw":{"variants":["5% of data, full-data results via info gain maximization","MIG: 5% subset matches full instruction tuning","Greedy info gain: 5% data beats full tuning","0.45 GPU-hrs to match full-data SFT","5% Tulu3 data rivals full fine-tuning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000719,"raw_usage":{"total_tokens":3285,"prompt_tokens":1056,"completion_tokens":2229,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":2144}},"tokens_in":672,"tokens_out":2229,"duration_ms":14770,"temperature":1.0,"reasoning_tokens":2144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:59:13.335031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MIG on a ~10K-record pool once with the exact marginal gain of Eq. (9) and once with the gradient approximation of Eq. (10); if the selected subsets differ appreciably in composition or downstream benchmark scores, then the implemented algorithm is not the submodular greedy method whose (1-1/e) guarantee is claimed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes the (1-1/e) approximation guarantee for greedy submodular maximization, the theoretical license for MIG's iterative selection."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides QDIT, the second-best comparison method on Tulu3, which MIG outperforms by +2.20% average."}],"review_version":1}