1 Introduction↩︎

High-quality training data remains the primary driver behind the empirical success of large language models (LLMs) [1]–[4]. Recent work has shown that intrinsic properties of training data, including data quality, distributional composition, and sample difficulty, shape the learning trajectory and downstream generalization performance of LLMs [5]–[7]. Consequently, a plethora of data-centric strategies, including selection, filtering, and reweighting, have been proposed to curate more effective training distributions [8]–[10]. Despite their disparate formulations, these methods share a common objective: to enhance model robustness and generalization by optimizing over a set of admissible data distributions \(\mathcal{Q}\), rather than the raw empirical distribution [11].

However, a key mechanism governing data utility, which involves the dynamic interactions of the train-unit (defined as inter-batch or inter-sample interactions, where the latter is a degenerate case of the former with a batch size of 1) interactions that evolve throughout training, has been largely overlooked. The efficacy of a train-unit depends not only on its intrinsic properties but also on when it is presented relative to others, as early train-units can prime the model for later ones, creating dependencies that render the data non-exchangeable. Recent empirical studies confirm that data ordering substantially influences convergence and final performance in LLM training [12]–[14]. Yet these scheduling approaches remain largely heuristic; they lack a principled, optimization-grounded method to quantify the very interactions they seek to exploit. This leads to a core open question: how can we formally model dynamic train-unit interactions to derive optimal data schedules?

To address this gap, we introduce \(D^3\), a framework that reformulates data scheduling as a constrained optimization problem over a dynamic graph. We start from the principle that the optimal order should prioritize train-units that most effectively “prepare” the model for subsequent data. \(D^3\) makes this precise by modeling pairwise influence via look-ahead loss reduction: if training sample \(i\) now significantly lowers the future loss of train-unit \(j\), then \(i\) should precede \(j\). By estimating these directional effects throughout training, \(D^3\) maintains a dynamic influence graph that captures the evolving topology of train-unit dependencies. The training sequence is then derived as the solution that best respects this graph’s structure, ensuring the model follows a coherent, interaction-aware learning trajectory. Our contributions are summarized as follows:

• We propose \(D^3\), a data scheduling framework that formalizes sequence ordering as an optimization problem over a dynamic training influence graph.

• By providing a fundamental method to characterize asymmetric train-unit interactions, we reveal that these relationships dictate the necessity of a structured training sequence, addressing a significant gap in conventional distribution-centric approaches.

• Extensive numerical validations across multiple pre-training and post-training tasks show that \(D^3\) consistently improves the performance of LLMs with reasonable computation overheads.

2 Related Work↩︎

We organize related work into three categories: (i) sample-level data selection (reweighting) methods, (ii) domain-level reweighting approaches, and (iii) empirical studies that investigate the effects of data ordering during LLM training.

2.1 Domain-Level Data Mixture Optimization↩︎

Domain-level optimization determines the optimal composition of macroscopic data sources (e.g., web, code, academic text) for pretraining, moving beyond simple heuristics. Inspired by scaling laws [15], recent studies introduce automated, optimization-driven frameworks. A seminal approach is DoReMi [7], which uses a small proxy model to derive domain weights via distributionally robust optimization. Subsequent methods enhance efficiency and scalability: REGMIX [16] treats the problem as a regression task using micro-models, MixMin [17] formalizes mixture finding as a convex minimization problem. Notably, MixMin demonstrates that optimal mixtures found on small models can be scale-invariant. To reduce retraining costs, Chameleon [18] utilizes leverage scores in a learned embedding space for flexible domain reweighting, and Velocitune [19] adaptively adjusts weights based on learning velocity, specifically targeting the complexities of domain-adaptive continual pre-training. In comprehensive empirical studies, [20] propose scaling laws for optimal data mixtures, further establishing the theoretical foundation for these data-centric strategies.

2.1.0.1 Sample-level Data Strategies.

Sample-level strategies prioritize individual training instances, offering finer-grained control than domain-level methods. A key recent advance is the shift toward dynamic, online selection mechanisms. GREATS [21] applies greedy optimization via Taylor expansion to select high-quality batches in every iteration, while [22] introduces online loss-based reweighting to focus training on more informative samples. To capture the complex interactions between data points, Group-MATES [23] proposes group-level selection using a relational data influence model. Another paradigm leverages training artifacts and optimization frameworks to refine data importance. AutoMixer [24] utilizes checkpoint models to approximate data influence, whereas DWM [25] implements a bi-level optimization framework to update a Data Weighting Model dynamically. Furthermore, to resolve potential conflicts between heterogeneous selection criteria, Multi-Actor Collaboration frameworks [26] have been proposed to integrate multiple prioritization rules through a central console. However, most existing sample-level methods either incur heavy computational overhead due to second-order optimizations or lack a unified geometric principle to guide the data selection process, particularly during critical phases such as model annealing.

2.2 Data Curriculum in LLM training↩︎

Previous methods have empirically validated the importance of sample ordering in LLM training [12]–[14]. Orca [27] establishes a progressive learning paradigm that leverages complex explanation traces to enhance reasoning capabilities. Recent research on contrastive post-training shows that a curriculum transitioning from easy preference pairs to hard ones yields step-function improvements in model alignment [28]. Despite these empirical successes, most curriculum strategies remain grounded in heuristic designs. There is still a lack of fundamental understanding regarding the underlying training dynamics, particularly how asymmetric gradient interactions between samples influence the optimization trajectory.

3 Methodology↩︎

In this section, we begin with a formal formulation of learning with data scheduling. In Section 3.2, we introduce the construction of an influence graph, which captures how loss curvatures induce asymmetric dependencies among training units. Subsequently, in Section 3.3, we formulate the data scheduling task as a constrained optimization problem governed by the influence graph. Section 3.4 presents an efficient solver for this problem. Finally, the implementation of \(D^3\) is detailed in Section 3.5, which focuses on the practical approximations designed to ensure scalability and efficiency in large-scale training settings.

3.1 Problem Formulation↩︎

We formalize one epoch of LLM training as a discrete dynamical system over the parameter space \(\Theta \subseteq \mathbb{R}^d\). Given a training dataset \(\mathcal{D} = \{z_i\}_{i=1}^N\), we consider a fixed partition into \(K\) disjoint batches \(\mathcal{P} = \{\mathcal{B}_1, \dots, \mathcal{B}_K\}\) of equal size \(B = N/K\) (assuming \(N\) is divisible by \(K\)). The empirical risk on a batch \(\mathcal{B} \in \mathcal{P}\) is defined as: \(\ell(\mathcal{B}; \theta) \;=\; \frac{1}{B} \sum_{z \in \mathcal{B}} \ell(z; \theta).\) A data schedule is specified by a permutation \(\pi \in \mathcal{S}_K\), where \(\mathcal{S}_K\) denotes the symmetric group of degree \(K\). When \(B = 1\) (hence \(K = N\)), the schedule operates at the sample level; for \(B > 1\), it characterizes batch-level scheduling. At each discrete step \(t \in \{1, \dots, T\}\), where \(T = K\) for one epoch, the model state is updated by a stochastic gradient operator \(\mathcal{T}_{\pi(t)}: \Theta \to \Theta\): \[\theta^{(t)} \;=\; \mathcal{T}_{\pi(t)}\bigl(\theta^{(t-1)}\bigr) \;=\; \theta^{(t-1)} - \eta \, \nabla_{\!\theta}\, \ell\bigl(\mathcal{B}_{\pi(t)}; \theta^{(t-1)}\bigr),\] where \(\eta > 0\) is the learning rate. The terminal state after processing all \(K\) batches is the composition: \[\theta^{(T)}(\pi) \;=\; \bigl(\mathcal{T}_{\pi(T)} \circ \mathcal{T}_{\pi(T-1)} \circ \cdots \circ \mathcal{T}_{\pi(1)}\bigr)(\theta^{(0)}).\] Because gradient operators are generally non-commutative in non-convex landscapes, the terminal state \(\theta^{(T)}(\pi)\) is path-dependent: different permutations \(\pi\) lead to different final parameters and hence different generalization performance. The data scheduling problem aims to find a permutation that minimizes the expected risk on a test distribution \(\mathcal{D}_{\text{test}}\): \[\pi^* \;=\; \arg\min_{\pi \in \mathcal{S}_K} \mathbb{E}_{z \sim \mathcal{D}_{\text{test}}}\Bigl[\,\ell\bigl(z; \theta^{(T)}(\pi)\bigr)\Bigr].\] We emphasize that this is a combinatorial optimization over \(K!\) possible schedules, which is intractable for large \(K\). Our work seeks efficient algorithms to approximate \(\pi^*\) by exploiting the interaction between training batches.

3.2 The Construction of Influence Graph↩︎

To characterize the interactions among training batches during optimization, we introduce the concept of training influence prediction. This measure, formally defined below, predicts how the loss of one training unit would change if the model were updated using the gradient of another one.

By varying \(\gamma\), this formulation allows us to probe interactions at different temporal scales: small values of \(\gamma\) reflect short-term and local effects, while larger values of \(\gamma\) approximate accumulated and long-term influences.

Intuitively, more negative influence values correspond to greater loss decrement on \(\mathcal{B}_j;\) resulted from the gradient descent on \(\mathcal{B}_i\). We have the following second-order approximation of the training influence in Proposition 1, which shows that training influence is symmetric to the first order but becomes asymmetric when curvature effects are considered.

Obviously, the first-order influence term is pairwise symmetric: \(\mathcal{I}_{i \to j}^{(1)}(t) = \mathcal{I}_{j \to i}^{(1)}(t),\) while the second-order influence term is asymmetric: \(\mathcal{I}_{i \to j}^{(2)}(t) \ne \mathcal{I}_{j \to i}^{(2)}(t),\) due to the per-batch Hessian \(\nabla_\theta^2 \ell(\mathcal{B}_j;\theta^{(t)})\).

At the same time, since \(\mathcal{I}_{i \to j}(t)\) depends on the current parameter state \(\theta^{(t)}\), the above interaction evolves throughout optimization, naturally inducing a dynamic and directed relation among training samples, which can be further characterized as a dynamic directed graph structure.

3.3 Influence Graph-Constrained Optimization↩︎

The influence graph \(\mathcal{G}^{(t)}\) (Definition 2) captures asymmetric dependencies among batches, but it does not directly prescribe an ordering for sequential training. To determine an optimal sequence, we transform the graph into a linear chain that respects strong directional preferences while resolving conflicts from cycles. We formalize these preferences using a directional advantage matrix that quantifies the relative benefit of training one batch before another.

An edge \((i,j)\) with positive directional advantage \(\mathbf{S}^{(t)}_{ij} > 0\) corresponds to \(\mathcal{I}_{i \to j}(t) < \mathcal{I}_{j \to i}(t)\), indicating that training batch \(\mathcal{B}_i\) before \(\mathcal{B}_j\) yields greater cumulative loss improvement than the reverse order. The set of dominance constraints is therefore \[\mathcal{E}^{(t)}_{\mathrm{dom}} := \{(i,j) \mid \mathbf{S}^{(t)}_{ij} > 0\} = \{(i,j) \mid \mathcal{I}_{i \to j}(t) < \mathcal{I}_{j \to i}(t)\}.\]

Transforming the fully connected influence advantage graph into a linear chain incurs a cost. Each edge with positive directional advantage that is contradicted by the ordering contributes a penalty.

Formally, let \(\pi^{(t)} \in \mathcal{S}_K\) be a batch ordering, where \(\pi^{(t)}(s)=k\) indicates that batch \(\mathcal{B}_k\) is placed at position \(s\). Define its inverse mapping \(\sigma^{(t)}: \{1,\dots,K\} \to \{1,\dots,K\}\) by \(\sigma^{(t)}(k)=s\) whenever \(\pi^{(t)}(s)=k\); then \(\sigma^{(t)}(k)\) gives the position of batch \(\mathcal{B}_k\). Both \(\pi^{(t)}\) and \(\sigma^{(t)}\) are bijections and belong to \(\mathcal{S}_K\), representing the same ordering. Using \(\sigma^{(t)}\) as the decision variable, the scheduling problem minimizes the total penalty from violated directional advantages: \[\sigma^{(t)\star} = \arg\min_{\sigma \in \mathcal{S}_K} \sum_{i \ne j} \max\!\bigl(0, \,\mathbf{S}^{(t)}_{ij}\bigr) \cdot \mathbb{I}\bigl[\sigma(j) < \sigma(i)\bigr].\] If \(\mathbf{S}^{(t)}_{ij} > 0\) (i.e., edge \((i,j)\) favors \(i\) before \(j\)) but \(\sigma(j) < \sigma(i)\) in the ordering, the edge is violated and incurs cost \(\mathbf{S}^{(t)}_{ij}\). When the graph is acyclic, there exists an ordering with zero cost, corresponding to a topological sort of the graph; otherwise, cycles force trade-offs, and the optimal ordering minimizes the total violation penalty.

3.4 Solving the Scheduling Optimization↩︎

We propose a lightweight solver, Random-Swap Refinemen (RSR), to approximately minimize the violation cost. The solver operates in two stages: first, it computes an initial ordering based on the advantage matrix row sums; second, it refines this ordering through random pairwise swaps.

3.4.0.1 Initial ordering via row sums.

For each batch \(i\), compute the row sum \(r_i = \sum_{j=1}^K \mathbf{S}^{(t)}_{ij}\). Since a positive entry \(\mathbf{S}^{(t)}_{ij}\) indicates that placing \(i\) before \(j\) is beneficial, a larger \(r_i\) suggests that batch \(i\) has a global advantage when scheduled earlier. We therefore sort the batches in decreasing order of \(r_i\) to obtain an initial permutation \(\pi_0\).

3.4.0.2 Random-swap refinement.

Starting from \(\pi_0\), we perform up to \(M\) random pairwise swap trials. In each trial, we randomly choose two distinct positions \(p\) and \(q\) (with \(p<q\)) and consider swapping the batches at these positions. Let \(i = \pi(p)\) and \(j = \pi(q)\). The change in violation cost \(\Delta\mathcal{C}\) due to swapping \(i\) and \(j\) can be computed efficiently by observing that only the relative order of \(i\) and \(j\) with respect to each other and to the batches between them changes. Specifically, let \(I(p,q) = \{\pi(k) \mid p < k < q\}\) be the set of batches between positions \(p\) and \(q\). Then: \[\Delta\mathcal{C} = \mathbf{S}^{(t)}_{ij} + \sum_{k \in I(p,q)} \bigl(\mathbf{S}^{(t)}_{ik} + \mathbf{S}^{(t)}_{kj}\bigr).\] If \(\Delta\mathcal{C} < 0\), the swap is accepted and \(\pi\) is updated accordingly.

3.4.0.3 Complexity analysis.

While this random‑swap heuristic does not guarantee global optimality, it provides a computationally efficient method to construct a high‑quality ordering that respects most directional advantages. The initial ordering requires computing all row sums and sorting, which takes \(O(K^2)\) time. Each swap trial evaluates \(\Delta\mathcal{C}\) in \(O(|I(p,q)|)\) time, bounded by \(O(K)\) in the worst case. Hence, the total time for \(M\) trials is \(O(MK)\), and the overall complexity of the solver is \(O(K^2 + MK)\).

3.5 The Detailed Implementation of \(D^3\)↩︎

Efficient training influence scheduling for LLMs must address two scaling issues: a large sample count \(N\) and high-dimensional gradients \(\mathbb{R}^d\) (with \(d \sim 10^9\)–\(10^{12}\)). Computing pairwise influences and solving the exact ordering problem is infeasible at this scale. We therefore introduce two approximations: chunk-wise internal reordering and gradient compression for influence propagation.

3.5.0.1 Chunk-wise Internal Reordering.

To scale to large \(K\), we adopt a stochastic chunking strategy. At each step \(t\), we randomly sample \(L \ll K\) batches to form a chunk \(\mathcal{C}^{(t)}\). The two-stage solver is then applied within \(\mathcal{C}^{(t)}\) to reorder these \(L\) batches based on their \(L \times L\) advantage sub-matrix. Batches outside the chunk keep their relative order. This reduces per-step complexity from \(O(K^2)\) to \(O(L^2 + ML)\) and ensures all batches are gradually refined over time through repeated sampling.

3.5.0.2 Gradient information compression.

To handle extreme gradient dimensionality, we project each batch gradient into a low-dimensional manifold using a fixed Gaussian random matrix \(\mathbf{R} \in \mathbb{R}^{d \times k}\) (\(k \ll d\)). This Johnson–Lindenstrauss projection approximately preserves inner products with high probability [29]. For the gradient of batch \(\mathcal{B}_i\), denoted as \(\mathbf{g}^{(t)}_i = \nabla_\theta \ell(\mathcal{B}_i; \theta^{(t)})\), we compute its low-dimensional sketch \(\tilde{\mathbf{g}}^{(t)}_i = \mathbf{R}^\top \mathbf{g}^{(t)}_i \in \mathbb{R}^k\). The first-order influence term can then be efficiently approximated as: \[\mathcal{I}^{(1)}_{i \to j}(t) = \bigl(\mathbf{g}^{(t)}_j\bigr)^\top \mathbf{g}^{(t)}_i \;\approx\; \bigl(\tilde{\mathbf{g}}^{(t)}_j\bigr)^\top \tilde{\mathbf{g}}^{(t)}_i.\] This compressed inner product allows us to compute the advantage matrix entries \(\mathbf{S}^{(t)}_{ij}\) with \(O(dk + k)\) memory and time per pair, instead of \(O(d)\).

3.5.0.3 Hessian approximation.

For the second-order term, we avoid the full Hessian by adopting a diagonal approximation via Hutchinson estimation [30]. Using \(W\) Hutchinson vectors \(\mathbf{u}^{(w)} \sim \mathcal{N}(0, \mathbf{I}_d)\), we estimate the diagonal Hessian for batch \(\mathcal{B}_j\) as \[\hat{\mathbf{h}}^{(t)}_j = \frac{1}{W} \sum_{w=1}^{W} \mathbf{u}^{(w)} \odot \bigl( \nabla^2_\theta \ell(\mathcal{B}_j; \theta^{(t)}) \, \mathbf{u}^{(w)} \bigr),\] where \(\odot\) denotes the Hadamard product. To avoid storing the \(d\)-dimensional vector \(\hat{\mathbf{h}}^{(t)}_j\) for every batch, we project the curvature onto the gradient direction, obtaining a scalar measure: \[\lambda_j^{(t)} = \bigl(\mathbf{g}^{(t)}_j\bigr)^\top \operatorname{diag}\bigl(\hat{\mathbf{h}}^{(t)}_j\bigr) \, \mathbf{g}^{(t)}_j.\] We then approximate the second-order influence term as \(\mathcal{I}^{(2)}_{i \to j}(t) \;\approx\; \frac{\gamma^2}{2} \, \lambda_j^{(t)}\). Combining with the compressed first-order term yields the final efficient influence estimate: \[\mathcal{I}_{i \to j}(t) \;\approx\; - \gamma \, \bigl(\tilde{\mathbf{g}}^{(t)}_j\bigr)^\top \tilde{\mathbf{g}}^{(t)}_i \;+\; \frac{\gamma^2}{2} \, \lambda_j^{(t)}.\] In practice, we use a small \(W = 5\) which provides a good efficiency-accuracy trade-off.

3.5.0.4 The Overall Pipeline.

Based on the above approximations, as shown in Algorithm 2 and Figure 1, \(D^3\) operates through four sequential phases at each training step. We begin by sampling candidate micro-batches and computing their low-dimensional gradient representations. These representations are then used to construct a preference matrix based on directional influence scores between batches. The matrix is subsequently fed to the RSR solver to determine the optimal training order. Finally, model parameters are updated sequentially.

4 Experiments↩︎

In this section, we first describe the benchmarks and baselines to ensure reproducibility and fair comparison. The following subsections then present analyses of pretraining and post-training performance, component ablation studies, the effects of key hyperparameters, and computational efficiency. Extended experimental details and additional results are provided in Appendices 6 and 9, respectively.

4.1 Experimental Settings↩︎

4.1.0.1 Benchmarks.

We assess pre-training performance by measuring language modeling quality, with perplexity (PPL) as the primary metric. Following prior works [16], [31], we also benchmark on HellaSwag [32], PIQA [33], OBQA [34], COPA [35], and WinoGrande [36] for commonsense reasoning. In post-training, we assess reasoning on more complex tasks, using GSM8K [37] and MATH [38] for math reasoning, HumanEval [39] and MBPP for coding.

4.1.0.2 Baselines.

We validate our method across both pre-training and post-training stages, specifically focusing on supervised fine-tuning (SFT). For pre-training, we compare Uniform Sampling and Dynamic Loss [40] with representative domain reweighting baselines RegMix [16], Data Mixing Law [41], DoReMi [7] and DoGE [42]. The experiments follow the standard scaling laws by training GPT-2 architecture [15] on subsets of SlimPajama [43], and training LLaMA-based models [44] on the Pile [45]. In the post-training phase, following previous work [46], we select baselines across three key dimensions: (i) curriculum ordering, comparing easy-to-hard versus hard-to-easy sequences categorized by initial loss values; (ii) multi-domain joint tuning, which follows a progressive curriculum learning taxonomy [47]; and (iii) single-domain specialization limits (DSL), which establish performance ceilings for code, math, and general instruction following. The training set encompasses CodeAlpaca [48], GSM8K-RFT [49], and Alpaca-GPT4 [50].

4.2 Main Results↩︎

4.2.0.1 Pre-training Performance.

As summarized in Table 1, \(D^3\) outperforms all sample-level and domain-level baselines in both overall language modeling quality and aggregated reasoning performance. It achieves a 4.2% relative reduction in perplexity over the strongest baseline and obtains the highest scores in four out of five evaluation benchmarks. While showing a slight degradation on PIQA compared to the dynamic loss baseline, \(D^3\) delivers substantial gains on complex reasoning tasks, notably OBQA (+10.1%) and COPA (+2.4% over the strongest domain baseline). These results demonstrate two core advantages of our approach. First, \(D^3\) effectively addresses the granularity limitation of domain-level reweighting methods such as DoReMi and RegMix, which assign uniform utility weights to all samples within a domain. By implementing batch-level scheduling, \(D^3\) captures fine-grained, intra-domain utility diversity without incurring the prohibitive computational cost of per-sample selection. Second, the pronounced improvements on OBQA and COPA suggest that our dynamic graph-constrained scheduling shapes beneficial data trajectories. Unlike static mixing approaches, \(D^3\) navigates the data manifold under structural constraints, potentially prioritizing foundational knowledge transitions that enhance performance on later complex reasoning tasks.

4.2.0.2 Post-trainig Performance.

The SFT results in Table 2 reveal several key insights into effective data scheduling. First, they challenge the notion of a static optimal data order: both fixed curriculum strategies (loss low\(\to\)high and high\(\to\)low) underperform our adaptive approach, confirming that dynamic sequencing based on real-time model state is more critical than predefined difficulty levels. Second, the pronounced gains on structured tasks, notably MATH (+11.4%) and HumanEval (+8.0%) suggest that \(D^3\)’s graph-constrained scheduling effectively guides the model to acquire formal reasoning and coding patterns. Third, \(D^3\)’s superiority over standard MTL demonstrates that explicitly managing inter-task interference through fine-grained batch scheduling yields better coordination than naive data mixing. Importantly, \(D^3\) achieves this while maintaining computational efficiency, as it avoids the prohibitive cost of per-sample selection. These findings collectively indicate that \(D^3\) strikes an effective balance between domain specialization and multi-task generalization, advancing the Pareto frontier of model performance across diverse capabilities.

4.3 Ablation Study↩︎

We evaluate alternative configurations of \(D^3\)’s core modules to assess each component’s contribution. To this end, we analyze each design variant along two primary dimensions: evaluating its downstream performance and measuring its computational efficiency.

4.3.0.1 Impact of Influence Graph Approximations

The fidelity of the influence estimator is a critical determinant of the scheduling quality in the \(D^3\) framework. Figure 3 illustrates the Pareto frontier between perplexity reduction and relative training overhead across different approximation strategies. As observed, the first-order symmetric method incurs negligible computational cost but yields only limited performance gains. This limitation stems from its inability to characterize the asymmetric curvature of the loss landscape, which is essential for identifying directional influence between batches.

A significant gap is observed between the Fisher Information Matrix (FIM) [51] and the Diagonal Hessian approach. While the Fisher method introduces a moderate overhead of approximately 1.3\(\times\), its perplexity improvement remains suboptimal compared to the diagonal Hessian. Theoretically, the Fisher matrix serves as a statistical expectation of the Hessian under specific distribution assumptions. However, in the context of dynamic data scheduling, the scheduler requires a precise characterization of instantaneous interactions. The Fisher approximation tends to smooth out local curvature fluctuations, thereby providing less reliable signals for micro-batch reordering during the non-stationary phases of training.

In contrast, the \(D^3\) framework utilizing the diagonal Hessian estimation achieves a breakthrough in the optimal lower-right quadrant of the frontier. By directly sampling the local Hessian via the Hutchinson estimator, \(D^3\) successfully captures the asymmetric dominance relations between samples. As highlighted in Figure 3, this high-fidelity estimation leads to a 5.1% reduction in perplexity relative to the baseline. Although this precision comes with an 89.0% increase in relative training overhead per step, the substantial gain in convergence quality justifies the investment. This result confirms that the benefit of transitioning from passive stochastic sampling to influence-constrained active ordering outweighs the additional cost of second-order computation, ultimately facilitating more efficient foundation model pre-training.

4.3.0.2 Impact of Different Optimizers

The success of the \(D^3\) framework depends heavily on efficiently solving the induced optimization problem to find a high-quality training sequence. We evaluate several candidate solvers for this optimization problem, primarily focusing on the Row-Sum and Greedy Insertion baselines in comparison with our proposed Random-Swap Refinement. As evidenced by the results in Table 3, RSR achieves the most favorable optimization trajectory and produces the lowest perplexity among all tested methods. Although RSR increases training time, its superior performance justifies the overhead for those prioritizing final model quality.

4.4 Hyperparameter Study↩︎

We conduct experiments on the key hyper-parameters of \(D^3\) to understand their influence on training dynamics. First, we examine the gradient projection dimension \(k\), which defines the low-dimensional manifold for influence estimation. As shown in Figure 4 (a), performance is sensitive to this dimensionality: values below \(1000\) fail to capture sufficient gradient interactions, while dimensions exceeding \(10000\) introduce stochastic noise that masks the influence signal. The peak performance at \(k = 3500\), resulting in an 8.1% perplexity reduction, identifies the optimal signal-to-noise ratio for characterizing batch interactions. Second, we evaluate the impact of the scheduling window \(L\) on convergence quality. Figure 4 (b) illustrates that perplexity consistently decreases as the window expands, achieving a 9.3% gain at \(L=60\). This trend highlights the necessity of a global perspective in batch sequencing; a larger window allows the solver to coordinate sequences over a broader horizon, effectively mitigating the “short-sighted” conflicts found in local heuristics. These results suggest that increasing the scheduling resolution is a robust lever for enhancing the training efficiency of large-scale foundation models.

5 Conclusion↩︎

In this work, we introduced \(D^3\), a principled framework that optimizes the training trajectory of LLMs by exploiting the non-exchangeability of training samples. By formalizing second-order asymmetric interactions through a dynamic influence graph and employing scalable batch-level reordering, we demonstrate that “when a model learns” is as critical as “what it learns." Empirical results across pre-training and reasoning benchmarks confirm that \(D^3\) effectively accelerates convergence and improves performance, providing a path-dependent perspective for data-centric LLMs training.

Limitations↩︎

While \(D^3\) demonstrates significant empirical gains, certain constraints remain to be addressed in future work. The resource consumption could be further compressed through more advanced gradient flow techniques. More efficient ways to extract the scheduling signal, like layer-selective gradient compression in LLMs, have not been explored. Furthermore, our theoretical analysis of convergence acceleration is currently grounded in a simplified linear regression proxy to intuitively verify the method. Extending these guarantees to the high-dimensional, non-convex landscape of Transformers remains a fundamental theoretical challenge that warrants deeper investigation.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

6 Experimental Settings↩︎

6.1 Benchmarks↩︎

Following standard protocols in the literature, we evaluate our method across two distinct stages: pre-training and post-training.

6.1.0.1 Pretraining Evaluation.

For the pre-training stage, we conduct a comprehensive evaluation focusing on both intrinsic language modeling and downstream reasoning capabilities. Specifically, we first reserve \(10\%\) of the pre-training data as a held-out validation set to PPL, which serves as a direct indicator of the model’s convergence and linguistic mastery. The statistical profile of the corpus used in this stage is summarized in Figure 5. Complementing the internal PPL analysis, we further evaluate the model’s capabilities across several fundamental benchmarks for linguistic understanding and commonsense reasoning. Under a few-shot setting, we conduct evaluations on HellaSwag [32], PIQA [33], OpenBookQA [34], COPA [35], and WinoGrande [36]. These tasks are designed to scrutinize the model’s capacity for robust inference and world-knowledge retrieval, providing a holistic assessment of the pre-training quality without the need for task-specific fine-tuning.

6.1.0.2 Posttraining Evaluation.

To evaluate the model’s specialized capabilities after post-training, we further benchmark its performance on complex math reasoning and code generation tasks. Specifically, we use GSM8K [37] and MATH [38] to measure multi-step mathematical reasoning, and HumanEval [39] and MBPP [52] to evaluate functional correctness in programming. Table 4 provides a comprehensive summary of the statistics and characteristics of these evaluation datasets.

6.2 Training Datasets↩︎

Our selection of training corpora is strategically aligned with the parameter scale of the respective models. For GPT-2 Small and Medium, we employ SlimPajama, a highly refined and deduplicated corpus. Conversely, for the larger LLaMA-1.1B and LLaMA-3.2-3B models, we utilize The Pile. Given their significantly higher model capacity, these architectures are better suited to ingest the diverse and complex domain-specific knowledge (e.g., mathematics, legal documents, and scientific literature) provided by The Pile, thereby maximizing their multi-domain reasoning potential. The specific data sources and their respective proportions within each dataset are summarized in Table 5.

6.3 Backbone Models↩︎

We evaluate our proposed method across a spectrum of model scales and architectural designs, as summarized in Table 6. Our experiments cover two representative families: the GPT-2 series Medium, representing classic decoder-only Transformers with absolute positional embeddings, and the Llama series (1.1B), incorporating modern advancements such as Rotary Positional Embeddings (RoPE), SwiGLU activation functions, and Grouped-Query Attention.

6.4 Implement Details↩︎

Our experimental framework is implemented using FP16 mixed-precision training to optimize computational throughput on a cluster equipped with two NVIDIA H200 GPUs. For model optimization, we employ the Adam optimizer with hyper-parameters \(\beta_1 = 0.9\), \(\beta_2 = 0.999\), and \(\epsilon = 10^{-8}\), incorporating a weight decay coefficient of 0.01. The learning rate is managed via a cosine annealing scheduler, which begins with a 500-step linear warmup phase to a peak value of \(5.0 \times 10^{-4}\), before decaying to a minimum of \(1.0 \times 10^{-4}\). Regarding the configuration for influence estimation, we maintain a consistent batch size of 16 and fix the random seed to 32 to ensure reproducibility across all trials. A critical hyper-parameter in our framework is the scaling factor \(\gamma\), which governs the intensity of the directional constraints. Empirically, we observe that setting \(\gamma\) proportional to the learning rate \(\eta\), specifically \(\gamma = 10^2 \eta\), yields the most stable and superior performance across various tasks. The maximum gradient dimension \(k\) is specifically tuned for different architectures, set to 35,00 for GPT-series models and 5,000 for LlaMa-based experiments. All other training configurations follow the standard settings of the respective foundation model baselines to ensure a fair comparison.

7 Algorithmic Details of Candidate Solvers↩︎

In this section, we delineate the algorithmic foundations of the candidate solvers used to optimize the influence-aware scheduling objective. Each solver represents a distinct trade-off between computational complexity and the capacity to resolve non-transitive influence cycles. We consider three approaches: Row-Sum Sorting, Greedy Insertion, and the Random-Swap Refinement solver proposed in Section 3.4.

7.0.0.1 Row-Sum Sorting (RS).

This baseline approach reduces the graph-structured optimization problem to a simple scalar ranking. For each batch \(i\), we compute its aggregate advantage score as the row sum of the directional advantage matrix: \[u_i = \sum_{j=1}^{K} \mathbf{S}^{(t)}_{ij}.\] Since \(\mathbf{S}^{(t)}_{ij} > 0\) indicates that placing batch \(i\) before \(j\) yields greater loss reduction than the reverse order, a larger \(u_i\) suggests that batch \(i\) exerts stronger global positive influence when scheduled earlier. The schedule \(\pi\) is generated by sorting batches in descending order of \(u_i\). The time complexity is \(O(K^2)\) for computing all row sums plus \(O(K \log K)\) for sorting, totaling \(O(K^2)\).

7.0.0.2 Greedy Insertion (GI).

To better capture local dominance relations while maintaining tractability, the Greedy Insertion solver constructs the sequence incrementally. Starting with an empty schedule \(\pi = [\,]\), at each step \(s = 1, \dots, K\), the algorithm selects the batch that maximizes its total advantage over all remaining (unscheduled) batches: \[i^* = \arg\max_{i \in \mathcal{C}} \sum_{j \in \mathcal{C} \setminus \{i\}} \mathbf{S}^{(t)}_{ij},\] where \(\mathcal{C}\) denotes the set of batches not yet scheduled. The selected batch \(i^*\) is appended to \(\pi\), and removed from \(\mathcal{C}\). This process repeats until \(\mathcal{C}\) is empty. The GI strategy has time complexity \(O(K^2)\) but often produces higher-quality schedules than RS by considering pairwise relations during construction.

7.0.0.3 Random-Swap Refinement (RSR).

As detailed in Section 3.4, our proposed solver begins with an initial ordering (e.g., from RS or GI) and iteratively improves it through random pairwise swaps. In each iteration, two distinct positions \(p\) and \(q\) (\(p < q\)) are chosen uniformly at random. Let \(i = \pi(p)\) and \(j = \pi(q)\). The change in total violation cost \(\Delta\mathcal{C}\) resulting from swapping \(i\) and \(j\) is computed as: \[\Delta\mathcal{C} = \mathbf{S}^{(t)}_{ij} + \sum_{k \in I(p,q)} \bigl( \mathbf{S}^{(t)}_{ik} + \mathbf{S}^{(t)}_{kj} \bigr),\] where \(I(p,q) = \{\pi(m) \mid p < m < q\}\) is the set of batches between positions \(p\) and \(q\) in the current schedule. If \(\Delta\mathcal{C} < 0\), the swap is accepted; otherwise, the current schedule is retained. This process continues for a predefined number of iterations \(T\), yielding a total complexity of \(O(K^2 + TK)\). The RSR solver effectively escapes local optima and can resolve complex cycles through its stochastic exploration of the permutation space.

7.1 Numerical Illustration↩︎

We provide a concrete illustration with \(K=5\) micro-batches. The directional advantage matrix \(\mathbf{S}\) contains a non-transitive cycle among batches 3, 4, and 5: \[\mathbf{S} = \begin{bmatrix} 0 & -10 & 2 & 1 & 8 \\ 10 & 0 & 1 & 0 & 2 \\ -2 & -1 & 0 & 10 & -5 \\ -1 & 0 & -10 & 0 & 10 \\ -8 & -2 & 5 & -10 & 0 \end{bmatrix}.\] Our objective is to maximize \(\mathcal{F}(\pi) = \sum_{i < j} \mathbf{S}_{\pi(i)\pi(j)}\).

7.1.0.1 Row-Sum Sorting.

The row sums are \(u = [1, 13, 2, -1, -15]\). Sorting in descending order yields \(\pi_{\text{RS}} = [2, 3, 1, 4, 5]\). The objective value is \(\mathcal{F}(\pi_{\text{RS}}) = 35\).

7.1.0.2 Greedy Insertion.

The algorithm proceeds as follows. Step 1: \(\mathcal{C}=\{1,2,3,4,5\}\). Batch 2 has the highest total advantage (13) and is scheduled first. Step 2: \(\mathcal{C}=\{1,3,4,5\}\). Batch 1 has the highest advantage (11) and is scheduled second. Step 3: \(\mathcal{C}=\{3,4,5\}\). Batch 3 is selected (advantage 5). Step 4: \(\mathcal{C}=\{4,5\}\). Batch 4 is selected (\(\mathbf{S}_{4,5}=10 > \mathbf{S}_{5,4}=-10\)). Step 5: Batch 5 is appended. The final schedule is \(\pi_{\text{GI}} = [2, 1, 3, 4, 5]\) with \(\mathcal{F}(\pi_{\text{GI}}) = 35\).

7.1.0.3 Random-Swap Refinement.

Starting from \(\pi_0 = \pi_{\text{RS}} = [2,3,1,4,5]\), we perform sample swap trials. Trial 1 (swap positions 2 and 4): \(i=3, j=4, I=\{1\}, \Delta\mathcal{C} = \mathbf{S}_{3,4} + (\mathbf{S}_{3,1}+\mathbf{S}_{1,4}) = 10 + (-2+1) = 9 > 0\), swap rejected. Trial 2 (swap positions 3 and 5): \(i=1, j=5, I=\{4\}, \Delta\mathcal{C} = \mathbf{S}_{1,5} + (\mathbf{S}_{1,4}+\mathbf{S}_{4,5}) = 8 + (1+10) = 19 > 0\), rejected. Trial 3 (swap positions 1 and 3): \(i=2, j=1, I=\{3\}, \Delta\mathcal{C} = \mathbf{S}_{2,1} + (\mathbf{S}_{2,3}+\mathbf{S}_{3,1}) = 10 + (1-2) = 9 > 0\), rejected. The schedule remains \([2,3,1,4,5]\) with \(\mathcal{F}=35\). This example shows the solver’s local search nature; with more trials it can escape suboptimal configurations (e.g., \([2,1,4,3,5]\) achieves \(\mathcal{F}=37\)).

8 Formulations of Influence Estimation Methods↩︎

This section formally defines the influence functions evaluated in our experiments. All methods are based on the training influence prediction (Definition 1) and its second-order approximation (Proposition 1), trading off computational accuracy against efficiency.

8.0.0.1 Random Baseline

The random baseline follows a standard stochastic optimization procedure without any influence-based reordering. At each step \(t\), a random permutation \(\pi \in \mathcal{S}_K\) is generated to process training batches: \[\pi = \text{random\_permutation}([1, 2, \dots, K]).\]

8.0.0.2 First-Order Symmetric Method

This method characterizes influence solely through first-order gradient interactions. Using the approximate first-order term, the influence of batch \(i\) on batch \(j\) is defined as: \[\mathcal{I}^{(1)}_{i \to j}(t) = -\eta \, \nabla_\theta \ell(\mathcal{B}_j; \theta^{(t)})^\top \nabla_\theta \ell(\mathcal{B}_i; \theta^{(t)}) = -\eta \langle g_i, g_j \rangle,\] where \(g_i = \nabla_\theta \ell(\mathcal{B}_i; \theta^{(t)})\) denotes the mean gradient of batch \(i\), and \(\eta\) is the learning rate. This formulation is symmetric with respect to \(i\) and \(j\).

8.0.0.3 Fisher Information Matrix Method

The Fisher method approximates the per-batch Hessian through the Fisher information matrix computed over all batches. First, the empirical Fisher matrix is calculated: \[\text{FIM} = \frac{1}{K} \sum_{k=1}^K g_k g_k^\top.\] The influence is then obtained by combining the first-order inner product with a FIM-weighted second-order term: \[\mathcal{I}_{\text{Fisher}, i \to j}(t) = -\eta \langle g_i, g_j \rangle + \frac{\eta^2}{2} g_i^\top \text{FIM} \, g_j.\] Here, the second-order term approximates \(\mathcal{I}^{(2)}_{i \to j}(t)\) using the shared Fisher matrix instead of the batch-specific Hessian \(\nabla^2 \ell(\mathcal{B}_j; \theta^{(t)})\).

8.0.0.4 Diagonal Hessian via Hutchinson

The \(D^3\) framework achieves its highest precision using Sophia-based estimation. We employ the Hutchinson randomized estimator to approximate a shared diagonal Hessian via \(N=5\) samples of Hessian-vector products: \[\hat{h}_{\text{diag}} = \frac{1}{N} \sum_{k=1}^{N} u^{(k)} \odot (H u^{(k)}), \quad u^{(k)} \sim \mathcal{N}(0, I_d),\] where \(H\) is the Hessian of the total loss. For each batch \(j\), the curvature scalar is computed as \(\lambda_j = g_j^\top \text{diag}(\hat{h}_{\text{diag}}) g_j\). The influence is then approximated as: \[\mathcal{I}_{\text{Sophia}, i \to j}(t) = -\eta \langle g_i, g_j \rangle + \frac{\eta^2}{2} \lambda_j.\] Compared to heuristic scaling, this formulation provides a more principled characterization of the loss landscape geometry, albeit using a shared Hessian approximation and batch-specific curvature scalars.

9 More Results and Analysis↩︎

9.1 A Toy Example for Understanding \(D^3\)↩︎

To demonstrate the robustness of our framework under inconsistent constraints, we consider a minimal \(N=3\) case where dominance relations induce a directed cycle. At optimization step \(t\), we assume the sample-wise influence matrix \(\mathbf{A}^{(t)} \in \mathbb{R}^{3 \times 3}\) is given by \[\mathbf{A}^{(t)} = \begin{bmatrix} 0 & -0.3 & 0.1 \\ 0.2 & 0 & -0.4 \\ -0.1 & 0.3 & 0 \end{bmatrix},\] where each entry \(A^{(t)}_{ij} = \mathcal{I}_{i \to j}(t)\) represents the influence value following Definition 2. Under the dominance criterion where an edge \((i,j)\) exists if \(\mathcal{I}_{i \to j}(t) < \mathcal{I}_{j \to i}(t)\), we observe a set of pairwise constraints: \(A_{12} < A_{21}\) implies \((1,2) \in \mathcal{E}^{(t)}_{\mathrm{dom}}\), \(A_{23} < A_{32}\) implies \((2,3) \in \mathcal{E}^{(t)}_{\mathrm{dom}}\), and \(A_{31} < A_{13}\) implies \((3,1) \in \mathcal{E}^{(t)}_{\mathrm{dom}}\). Consequently, the dominance graph \(\mathcal{G}^{(t)}_{\mathrm{dom}}\) forms a directed cycle \(1 \to 2 \to 3 \to 1\), rendering any consistent topological ordering impossible.

To resolve this conflict, we compute the directional advantage matrix \(\mathbf{S}^{(t)} = \mathbf{A}^{(t)\top} - \mathbf{A}^{(t)}\), where \(S^{(t)}_{ij}\) quantifies the net benefit of training \(x_i\) before \(x_j\): \[\mathbf{S}^{(t)} = \begin{bmatrix} 0 & 0.5 & -0.2 \\ -0.5 & 0 & 0.7 \\ 0.2 & -0.7 & 0 \end{bmatrix}.\] Following the cost-minimization formulation in Section 3.3, we seek an ordering \(\sigma^{(t)\star} \in \mathcal{S}_3\), where \(\sigma(k)\) denotes the position assigned to sample \(x_k\), that minimizes the total penalty incurred by violated directional advantages: \[\sigma^{(t)\star} \;=\; \arg\min_{\sigma \in \mathcal{S}_3} \mathcal{C}(\sigma), \qquad \mathcal{C}(\sigma) \;=\; \sum_{i \ne j} \max\!\bigl(0,\, S^{(t)}_{ij}\bigr) \cdot \mathbb{I}\bigl[\sigma(j) < \sigma(i)\bigr].\] Only the three positive entries \(S_{12}=0.5\), \(S_{23}=0.7\), and \(S_{31}=0.2\) can contribute to the cost, each penalizing an ordering that places its preferred successor ahead of its predecessor. Writing each permutation as the resulting sequence of samples and evaluating \(\mathcal{C}(\sigma)\) over all \(\sigma \in \mathcal{S}_3\) yields: \[\begin{align} \mathcal{C}([1,2,3]) &= S_{31} = 0.2, \quad & \mathcal{C}([1,3,2]) &= S_{23} + S_{31} = 0.9, \\ \mathcal{C}([2,1,3]) &= S_{12} + S_{31} = 0.7, \quad & \mathcal{C}([2,3,1]) &= S_{12} = 0.5, \\ \mathcal{C}([3,1,2]) &= S_{23} = 0.7, \quad & \mathcal{C}([3,2,1]) &= S_{12} + S_{23} = 1.2. \end{align}\] The optimal schedule is thus \(\sigma^{(t)\star} = [1,2,3]\) with cost \(0.2\). This result illustrates that when faced with cyclic dominance, our cost-minimization formulation naturally sacrifices the weakest conflicting edge (in this case, \((3,1)\) with \(S_{31}=0.2\)) so as to preserve the two stronger directional preferences. Such a mechanism ensures training stability and efficiency even when local gradient alignments and Hessian curvatures induce inconsistent sample dependencies. \(\square\)

9.2 Pre-training on Larger Models↩︎

We evaluate the scalability and effectiveness of D\(^3\) by pre-training a 1.1B Llama-based model on 100B tokens of the Pile dataset. As illustrated in Table 7, D\(^3\) consistently outperforms both sample-level and domain-level baselines across nearly all evaluation dimensions. Specifically, D\(^3\) achieves a significant reduction in perplexity (2.53), representing a 4.1% relative improvement over the strongest baseline.

9.3 Theoretical Analysis: An example↩︎

We analyze the convergence properties under a linear regression setting with quadratic loss \(L(\theta) = \frac{1}{2N} \sum_{i=1}^N (y_i - \theta^\top x_i)^2\). Let \(\mathcal{C}_t\) denote the set of indices of samples not yet selected in the current epoch at step \(t\), with \(m_t = |\mathcal{C}_t|\).

10 Notation↩︎

References↩︎