REVIEW 5 major objections 5 minor 31 references
GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling
T0 review · 5 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read GRAFT selects a small MaxVol-chosen subset of each batch that it claims keeps the gradient direction intact, matching or beating recent selection baselines in accuracy and efficiency while cutting energy use.
desk verdict A promising empirical sampler whose theoretical guarantee rests on a false identity and whose algorithm contradicts its own adaptive design. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Fast MaxVol row sampling on the top-$R$ left singular vectors of each batch: given $V\in\mathbb{R}^{K\times R}$, it greedily selects rows by maximizing the volume of the induced $R\times R$ submatrix—equivalently, at step $j$ it chooses the row with the largest absolute entry of the residual $r_j = v_j - V(:,[1:j-1])\,V(p,[1:j-1])^{-1}v_{p,j}$, so each new row is the most extreme direction in the remaining feature space. This produces an interpolation matrix $T=VM^{-1}$ that the paper uses to argue selected rows reconstruct the whole batch. A second mechanism, dynamic rank adjustment, chooses $R$ by minimizing the projection error between subset and full-batch gradients.
What would settle it
Run greedy Fast MaxVol on a small real feature matrix—say $K=5$, $R=2$ from SVD embeddings of CIFAR-10 images—form $T=V V(S,:)^{-1}$ for the selected rows $S$, and check whether $\max_{i,j}|T_{ij}|\le 1$ and whether each column sums to $K/R$. Any column sum different from $K/R$ falsifies the proof's key premise; alternatively, compare measured $\|\nabla_\theta L(\theta;A)-\nabla_\theta L(\theta;A(S,:))\|_2$ against the claimed $(K/R)L_g\sigma_{R+1}$ bound.
Extended reading notes
Core claim
GRAFT's central mechanism is per-batch row sampling in feature space. For a batch $A\in\mathbb{R}^{K\times M}$, the method forms $V=U_R$, the top-$R$ left singular vectors, and runs a greedy Fast MaxVol routine to choose $R$ rows whose submatrix maximizes volume; the training update then uses only the gradients of those rows. To keep the subset faithful to the optimization dynamics, GRAFT periodically searches over candidate ranks and picks the smallest $R$ for which the projection error $\|\bar g - P_R\bar g\|_2^2$ of the full-batch average gradient onto the selected gradients is below a tolerance $\epsilon$. The paper claims this procedure matches or exceeds gradient-matching baselines acr
Load-bearing premise
The proof that selected samples approximate the full-batch gradient assumes that the MaxVol interpolation weights satisfy an exact column-sum identity ($\sum_i T_{ij}=K/R$) and an entry bound ($|T_{ij}|\le 1$); the greedy Fast MaxVol algorithm used in the method does not enforce either property.
Editorial extensions
If this is right
- At 25% of the data, the reported fidelity coefficient stays above 0.8 while emissions drop by roughly 60–70% compared with full training, so resource-constrained training becomes feasible on datasets previously out of reach.
- The per-iteration cost $O(KR^2)+O(|\mathcal{R}_{\rm set}|Rd)$ is independent of the dataset size $N$, so the method can be dropped into large-scale training loops that make gradient-matching baselines run out of memory.
- Because alignment increases during training, the dynamic rank mechanism makes later epochs cheaper automatically, giving a natural curriculum of shrinking subsets.
- Warm-start GRAFT on BERT/IMDB reaches within 0.18% of full-data accuracy using 35% of the data and roughly 41% less CO2, suggesting the method transfers to fine-tuning large language models.
Reading between the lines
- Editorial inference: the proof of Remark 1 (Supplementary §9, displayed equation (2)) relies on the interpolation-matrix identity $\sum_i T_{ij}=K/R$ and on $|T_{ij}|\le 1$ for the rows chosen by greedy Fast MaxVol; neither is guaranteed by the greedy selector, so the gradient bound is conditional unless one uses a MaxVol variant that enforces those weights or replaces this step with a different a
- Editorial inference: the projection-error criterion makes the method a per-batch difficulty probe: batches where even the best candidate rank $R$ cannot keep $\|\bar g-P_R\bar g\|_2^2\le\epsilon$ force larger subsets. This suggests a testable extension: use the chosen $R^*$ itself as a signal for distribution shift, noisy labels, or domain mismatch during training.
- Editorial inference: the paper's own Limitations section (§11) records that at 5% of CIFAR-100 accuracy falls from ~75% to ~41% and that performance depends on feature-extractor quality; these passages bound the efficiency claim and indicate the method's advantage lives at moderate compression levels.
- Editorial inference: the same fast MaxVol row selection applied to activations yields a preliminary channel-pruning result (Table 5: 50% of ResNet-18 channels, accuracy from 93.21% to 91.97%, ~1.7x faster inference). This is an implicit extension the paper mentions but does not develop.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes GRAFT, an in-training data-subset-selection method that projects each mini-batch into a low-rank feature space, selects rows via a fast MaxVol heuristic, and then adjusts the subset size using a gradient-projection criterion. The central claims are that the selected subset approximates the full-batch gradient (Remark 1, stated as ||∇θL(θ;A) − ∇θL(θ;A(S,:))||₂ ≤ (K/R)L_gσ_{R+1}), that dynamic rank adjustment preserves convergence (Theorem 1 and Corollary 1), and that the method is computationally efficient and reduces CO₂ emissions while matching or exceeding baseline accuracy. The paper includes experiments on CIFAR, TinyImageNet, Caltech256, FashionMNIST, DermaMNIST, and BERT fine-tuning, together with ablations on feature extractors and subspace-similarity comparisons. I assess whether the theoretical and algorithmic components actually support these claims.
Significance. If the theoretical guarantee and the algorithmic description were correct, GRAFT would be a practically relevant contribution to efficient deep learning, and the paper's attention to energy/CO₂ accounting is welcome. The experimental breadth is also a strength. However, the main theoretical bridge from MaxVol selection in feature space to gradient fidelity rests on a false MaxVol property, and the dynamic-rank mechanism as implemented appears to defeat its stated purpose. These are load-bearing issues for the paper's central claims. The empirical results might still support a heuristic method, but the manuscript as written does not provide a reliable theoretical or algorithmic basis for the claimed guarantees.
major comments (5)
- [Supplementary §9, proof of Remark 1] The proof asserts that the interpolation matrix T = V M⁻¹ satisfies Σᵢ Tᵢⱼ = K/R for every column j. This identity is false in general. Counterexample: K=3, R=2, V = [[1,0],[0,1],[0,0]] (valid orthonormal columns), with selected rows {1,2}; then T = V and column sums are 1 and 1, not K/R = 3/2. Moreover, the greedy Fast MaxVol algorithm of §3.1 does not guarantee the entry bound |Tᵢⱼ| ≤ 1; that property holds only for global volume maximizers. Consequently the step 'the terms involving T sum to zero' is unsupported and the bound ≤ (K/R)L_gσ_{R+1} does not follow. Since Remark 1 is the only stated link between feature-space MaxVol selection and gradient fidelity, the theoretical support for 'preserves the training trajectory' collapses.
- [§3.2, Algorithm 1 (Dynamic Rank Adjustment)] The pseudocode sets R* = arg min_{Ri} d_Ri with no constraint involving ε. The projection error d_Ri = ||¯g − P_Ri ¯g||² is nonincreasing in Ri for the nested sequential Fast MaxVol selection, so this rule always returns the largest candidate rank. This means the algorithm does not implement the described 'minimal number of dominant samples' or the reported rank reductions over training (Fig. 2b). The threshold ε appears in the prose but never in the code; Corollary 1's guarantee therefore does not apply to the implemented selection rule.
- [§4, Tables 2, 8–12 (GRAFT Warm)] GRAFT Warm is a named variant used in several headline comparisons, but no algorithmic definition is given. The text only mentions 'initialization with full-data representations' and reports warm-start behavior; there is no specification of how many epochs of full-data training are used, whether the selection period changes, or how the warm-start interacts with the dynamic rank. This is a reproducibility gap for a variant that is the best performer in several tables.
- [§3.3 Complexity Analysis and Algorithm 1] The complexity claim, 'no term scales with N', omits the cost of the selection stage. At every iteration with t mod S == 0, Algorithm 1 loops over all batches X_i in the dataset and computes the full-batch gradient ¯g_i for each batch. This is an O(ND)-cost full forward/backward pass over the entire dataset at each selection epoch. With S=20–50, this cost is not negligible and is absent from the reported per-iteration complexity and from the energy/emissions comparisons. The stated 'linear in K' claim is therefore misleading for selection iterations.
- [§3.2, Theorem 1 and Corollary 1] These results are conditional on the projection error bound ||¯g − Proj_{S_R}(¯g)|| ≤ ε, not on any property established from Fast MaxVol row selection. The proof of Remark 1 was the only mechanism connecting the chosen subset to that bound, and it is invalid. As a result, the convergence theorems state a general property of projected gradient descent under an assumption that the selection algorithm is not shown to satisfy.
minor comments (5)
- [Throughout] There are several internal cross-reference errors: 'Corollary 2' and 'Lemma 3' are cited in §3.2 but do not exist, and Corollary 1 is misnumbered relative to the text. Please correct all cross-references.
- [Algorithm 1] The input list includes 'feature matrices V' but neither the initial construction of V nor its refresh schedule appears in the pseudocode. The periodic 'basis/feature refresh' is mentioned only in the complexity section; without it, the algorithm is under-specified.
- [Table 1 and §3.3] The complexity expression uses R both as the active rank and as the maximum candidate rank; clarify the notation, e.g., R_max = max Rset, and state whether gradients for selected samples are included in the reported per-iteration cost.
- [Table 4] The subspace-similarity comparison on Iris reports a single number per method with no error bars or number of trials; the 84.6× speedup claim would be more credible with repeated measurements and more than one dataset.
- [Abstract and §4] Typographical issues: 'MaxV ol' appears in the abstract, the determinant formula in §3.1 has a formatting artifact, and the duplication of equation numbering (Eq. (3) in §9.4) should be fixed.
Circularity Check
No circularity found: the convergence guarantee is a conditional premise-enforcement statement, the empirical comparisons are self-contained, and the flawed MaxVol column-sum identity in Remark 1 is a correctness gap, not a circular derivation.
full rationale
I walked the paper's derivation chain and found no step where a claimed prediction or first-principles result reduces by construction to its own inputs, and no load-bearing self-citations. The central theoretical assertion, Remark 1 (Supplementary §9), tries to bound the gradient approximation error by constructing the MaxVol interpolation matrix T and invoking the column-sum identity Σ_i T_ij = K/R. That identity is false in general (and the greedy Fast MaxVol selector does not guarantee the |T_ij|≤1 bound), so the proof is unsupported. But a false or unproven lemma is a correctness risk, not circularity: the theorem does not assume its conclusion; it attempts an invalid derivation from external properties of MaxVol. The dynamic rank adjustment in Section 3.2 and Algorithm 1 computes the full-batch gradient, evaluates the projection error ∥¯g−P_R ¯g∥ for candidate ranks, and picks R* minimizing that error. Corollary 1 then states that if the measured projection error is ≤ε, convergence follows. This is self-referential in an engineering sense—the method checks the quantity it wants to keep small—but it is not circular: the algorithm uses the full-batch gradient as a validation/selection signal, does not rename a fitted parameter as an independent prediction, and does not make an Eq.-X-equals-Eq.-Y identification. The convergence theorem is a standard conditional result; the algorithm simply enforces its premise on the current batch. The empirical accuracy, efficiency, and CO2 comparisons are against external benchmarks and baselines and do not depend on any fitted value being re-presented as a prediction. No self-citation chain, imported uniqueness theorem, or ansatz-via-citation pattern is present. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
free parameters (5)
- candidate rank set R =
not reported in paper
- selection period S =
not reported per dataset (text says typically 20 to 50)
- projection error threshold epsilon =
not reported
- exponential gain parameters lambda, E0, H =
e.g., GRAFT lambda=3.2±0.4, GRAFT Warm E0=0.38±0.05
- feature extractor choice =
SVD in ablation, unspecified in main experiments
assumptions (5)
- domain assumption The gradient map g(x) = grad_theta L(theta; x) is L_g-Lipschitz in the input x.
- ad hoc to paper Fast MaxVol-selected rows satisfy exact maxvol interpolation properties: |T_ij|<=1, ||T_i,:||_1<=R, and sum_i T_ij = K/R.
- domain assumption The SVD low-rank representation V=U_R captures the dominant subspace so that MaxVol-selected rows of V correspond to influential samples in A.
- domain assumption Projection error bound ||gbar_i - G_R G^dagger_R gbar_i||^2 <= epsilon^2 is achieved at every iteration by the dynamic rank adjustment.
- standard math Standard smoothness (C-smooth) and bounded-variance assumptions for SGD (A1)-(A2).
Cite this review
Pith. "Pith review of GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling." pith.science (2026). https://pith.science/paper/5FXGVTUH
@misc{pith2026250813653,
author = {Pith},
title = {Pith review of: GRAFT: Gradient-Aware Fast MaxVol Technique for Dynamic Data Sampling},
year = {2026},
howpublished = {\url{https://pith.science/paper/5FXGVTUH}},
note = {Machine review of arXiv:2508.13653}
}
abstract
Training modern neural networks on large datasets is computationally and environmentally costly. We introduce GRAFT, a scalable in-training subset selection method that (i) extracts a low-rank feature representation for each batch, (ii) applies a Fast MaxVol sampler to select a small, diverse subset that spans the batch's dominant subspace, and (iii) dynamically adjusts the subset size using a gradient-approximation criterion. By operating in low-rank subspaces and training on carefully chosen examples instead of full batches, GRAFT preserves the training trajectory while reducing wall-clock time, energy consumption, and $\mathrm{CO}_2$ emissions. Across multiple benchmarks, GRAFT matches or exceeds recent selection baselines in both accuracy and efficiency, providing a favorable trade-off between accuracy, efficiency, and emissions.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Deep Learning on a Data Diet: Finding Important Examples Early in Training
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. “Deep Learning on a Data Diet: Finding Important Examples Early in Training”. In: arXiv preprint arXiv:2107.07075 (2021)
arXiv 2021
-
[2]
An empirical study of example forgetting during deep neural network learning
Mariya Toneva et al. “An empirical study of example forgetting during deep neural network learning”. In: International Conference on Learning Representations. 2018
work page 2018
-
[3]
Selection via proxy: Efficient data selection for deep learning
Cody Coleman et al. “Selection via proxy: Efficient data selection for deep learning”. In: Proceedings of the 37th International Conference on Machine Learning (ICML). PMLR, 2020, pp. 2226–2236
work page 2020
-
[4]
DRoP: Distributionally Robust Data Pruning
Artem M. Vysogorets, Kartik Ahuja, and Julia Kempe. “DRoP: Distributionally Robust Data Pruning”. In: Proceedings of the Thirteenth International Conference on Learning Representations (ICLR). To appear. 2025. URL: https://openreview.net/forum?id= fxv0FfmDAg
work page 2025
-
[5]
GradMatch: Gradient Matching Based Data Subset Selection for Efficient Deep Model Training
Krishnavarun Killamsetty et al. “GradMatch: Gradient Matching Based Data Subset Selection for Efficient Deep Model Training”. In: ICML. 2021. 21
work page 2021
-
[6]
Glister: Generalization based data subset selection for efficient and robust learning
K. Killamsetty et al. “Glister: Generalization based data subset selection for efficient and robust learning”. In: Proceedings of the AAAI Conference on Artificial Intelligence. V ol. 35. 2021, pp. 8110–8118
work page 2021
-
[7]
Coresets for Data-efficient Training of Machine Learning Models
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. “Coresets for Data-efficient Training of Machine Learning Models”. In: ICML. 2020
work page 2020
-
[8]
Deep batch active learning by diverse, uncertain gradient lower bounds
Jordan T Ash et al. “Deep batch active learning by diverse, uncertain gradient lower bounds”. In: International Conference on Learning Representations (ICLR). 2020
work page 2020
Show all 31 references
-
[9]
Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning
Xiaobo Xia et al. “Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning”. In: International Conference on Learning Representations (ICLR). 2023
2023
-
[10]
Dataset distillation: A comprehensive review
Boqing Zhao et al. “Dataset distillation: A comprehensive review”. In: arXiv preprint arXiv:2112.10963. 2021
2021 arXiv
-
[11]
SelMatch: Selection-based Dataset Distillation via Trajectory Matching
Kyungmin Lee et al. “SelMatch: Selection-based Dataset Distillation via Trajectory Matching”. In: International Conference on Learning Representations (ICLR). 2024
2024
-
[12]
Efficient data subset selection to generalize training across models: Transductive and inductive networks
Eeshaan Jain et al. “Efficient data subset selection to generalize training across models: Transductive and inductive networks”. In:Advances in Neural Information Processing Systems 36 (2023), pp. 4716–4740
2023
-
[13]
Column subset selection and Nyström approximation via continuous optimization
Anant Mathur, Sarat Moka, and Zdravko Botev. “Column subset selection and Nyström approximation via continuous optimization”. In: 2023 Winter Simulation Conference (WSC). IEEE. 2023, pp. 3601–3612
2023
-
[14]
Incomplete cross approximation in the mosaic-skeleton method
E.E. Tyrtyshnikov. “Incomplete cross approximation in the mosaic-skeleton method”. In: Computing 64.4 (2000), pp. 367–380
2000
-
[15]
How to find a good submatrix
S. A. Goreinov et al. “How to find a good submatrix”. In: Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub. World Scientific, 2010, pp. 247– 256
2010
-
[16]
Optimization for machine learning
Léon Bottou, Frank E Curtis, and Jorge Nocedal. “Optimization for machine learning”. In: SIAM Review 60.2 (2018), pp. 223–311
2018
-
[17]
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions”. In: SIAM Review 53.2 (2011), pp. 217–288
2011
-
[18]
Matrix Computations
Gene H Golub and Charles F Van Loan. Matrix Computations. JHU Press, 2013
2013
-
[19]
Eco2ai: carbon emissions tracking of machine learning models as the first step towards sustainable ai
S. A. Budennyy et al. “Eco2ai: carbon emissions tracking of machine learning models as the first step towards sustainable ai”. In: Doklady Mathematics (2022), S118–S128
2022
-
[20]
CIFAR-10 and CIFAR-100 Datasets
Alex Krizhevsky and Geoffrey Hinton. CIFAR-10 and CIFAR-100 Datasets. https://www. cs.toronto.edu/~kriz/cifar.html. Accessed: 2024-11-02. 2009
2024
-
[21]
Tiny ImageNet Visual Recognition Challenge
Li Fei-Fei et al. Tiny ImageNet Visual Recognition Challenge. https://www.kaggle.com/ c/tiny-imagenet. Accessed: 2025-05-15. 2015
2025
-
[22]
Caltech-256 Object Category Dataset
Gregory Griffin, Alex Holub, and Pietro Perona. “Caltech-256 Object Category Dataset”. In: California Institute of Technology. Accessed: 2025-05-15. 2007
2025
-
[23]
Teneva: A Fast and Efficient Tensor Decomposition Library
AndreiChertkov. Teneva: A Fast and Efficient Tensor Decomposition Library . https : / / github.com/AndreiChertkov/teneva. Accessed: 2025-05-15. 2025
2025
-
[24]
The Use of Multiple Measurements in Taxonomic Problems
Ronald A. Fisher. “The Use of Multiple Measurements in Taxonomic Problems”. In: Annals of Eugenics 7.2 (1936), pp. 179–188. DOI: 10.1111/j.1469-1809.1936.tb02137.x
1936
-
[25]
Aggregated residual transformations for deep neural networks
S. Xie et al. “Aggregated residual transformations for deep neural networks”. In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2017, pp. 1492–1500
2017
-
[26]
Krizhevsky, G
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. Internet, 2009
2009
-
[27]
Visualizing the loss landscape of neural nets
H. Li et al. “Visualizing the loss landscape of neural nets”. In: Advances in neural information processing systems 31 (2018)
2018
-
[28]
Mobilenetv2: Inverted residuals and linear bottlenecks
M. Sandler et al. “Mobilenetv2: Inverted residuals and linear bottlenecks”. In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2018, pp. 4510–4520
2018
-
[29]
Chapter 5 - Text Mining Methodology
Gary Miner et al. “Chapter 5 - Text Mining Methodology”. In: Practical Text Mining and Statistical Analysis for Non-structured Text Data Applications. Boston: Academic Press, 2012, pp. 73–89. ISBN : 978-0-12-386979-1. DOI: https://doi.org/10.1016/B978- 0- 12- 386979- 1.00005- ...
2012 doi
-
[30]
A review of algorithms for SAW sensors e-nose based volatile compound identification
Olivier Hotel et al. “A review of algorithms for SAW sensors e-nose based volatile compound identification”. In: Sensors and Actuators B: Chemical 255 (2018), pp. 2472–2482. ISSN : 0925-4005. DOI: https : / / doi . org / 10 . 1016 / j . snb . 2017 . 09 . 040. URL: https : //ww...
2018
-
[31]
Analysis of complex mixtures using high-resolution nuclear magnetic resonance spectroscopy and chemometrics
J. S. McKenzie et al. “Analysis of complex mixtures using high-resolution nuclear magnetic resonance spectroscopy and chemometrics”. In: Progress in Nuclear Magnetic Resonance Spectroscopy 59.4 (2011), pp. 336–359. 23
2011
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.