acceptodds
Under review as a conference paper at ICLR 2027

TOKEN MARKOV GRAPHS FOR DATA-EFFICIENT LANGUAGE MODEL PRETRAINING

Abstract

The cost of pretraining a language model is set by the tokens, and the wall-clock time, needed to reach a target loss, and high-quality text is becoming the binding resource. We introduce the Token Markov Graph (TMG), a directed graph of token-transition counts computed once from the pretraining corpus, and inject it into pretraining as an annealed graph-distillation loss or as a lightweight architectural memory module. TMG reduces the tokens needed to reach the baseline’s final validation loss at and below the Chinchilla-optimal budget. At the Chinchillaoptimal budget, the architectural route (engram v1) needs 8.1% fewer tokens and 5.1% less wall-clock time, with a gain in all 9 seeds (t(8) = 7.61, 4.56, and 3.05 for tokens, wall-clock time, and final loss gap). At a fixed 100M-token budget, curvature-weighted distillation saves 14.2–20.0% of tokens for models from 172M to 3B parameters (minimum t = 4.83 on the loss gap), with token savings, and wall-clock savings of up to 20.9%, growing with model size. The gains hold under a tuned baseline learning rate, on two independently built graphs, and on code-only training (6 seeds, t(5) = 3.96), and carry over to next-word cloze completion. Because the graph is built once and reused across models and runs, corpus transition statistics offer an inexpensive, broadly applicable accelerant for pretraining.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Token Markov Graph, LLM Pretraining Efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jdNoOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposed Token Markov Graph (TMG), a local co-occurrence statistics counted from the pretraining corpus, which can be used to accelerate early language-model training through two ways: adding a KL loss to the training loss, mixing the hidden state with weighted combination of successor embeddings.

The authors evaluate their methods on transformers (Gemma2 architecture) ranging from 172M to 3B parameters. Their graphs are constructed from 60B and 350B tokens with sequence length 512 and weight decay 0.1. They train the transformers on 100M tokens with a single epoch.

Critical strengths
  • Using counted statistics rather than a trained neural teacher is elegant.
  • It's good to show experiment results with multiple seeds and check statistical significance.
Critical weaknesses
  • This paper is a bit outdated. Every reference is from before 2025 except one citation (the engram paper), even though data-efficient pretraining is a topic with many relevant work from 2025 and 2026.
  • Data-constrained pretraining Literatures, including Muennighoff et. al. usually train an overparameterized model on a fixed data budget for multiple epochs. This paper only trains on 100M unique tokens for one epoch, which is an unusual setup. 100M is a very small budget for single-epoch pretraining: In LLM pretraining, it is common that some method outperforms at first but then the gain diminishes as training continues.
Questions for authors
  • Why you only train the model on 100M tokens for a single epoch?
  • Why you didn't disclose how the 100M tokens were sampled? Is it a subset of DCLM or C4?
  • Table 2 shows the gain increases with model size. Do the authors have any understanding on this?
  • The model architecture, Gemma2, is an old architecture. The sequence length 512 is too short for pretraining. Why you chose Gemma2 and sequence length 512?
  • The calculation of Chinchilla-optimal budget seems incorrect. The authors used 20 * # of non-embedding parameters. Why not use 20 * # of (non-embedding parameters + embedding parameters)?
Reviewer_HrhkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Token Markov Graph (TMG), which captures token transition statistics from a large pretraining corpus and uses them to assist language model pretraining through graph distillation or an additional memory module. The experiments show that TMG can reduce the number of training tokens and wall-clock time required to reach the same validation loss.

Strengths

The paper addresses the important problem of improving pretraining efficiency. The proposed approach is relatively simple, and the authors demonstrate training efficiency improvements across different model sizes and multiple random seeds.

Weaknesses

  1. Insufficient evaluation of how efficiently TMG utilizes the additional data.

This is my main concern. The paper constructs TMG using 350B tokens but evaluates its effectiveness primarily on models trained with only 100M tokens. In other words, TMG incorporates statistical information from a corpus approximately 3,500 times larger than the actual training data. Given this substantial amount of additional information, the observed improvements are not particularly surprising. However, it remains unclear how effectively TMG utilizes this information.

I believe two important questions need to be addressed:

  • If TMG is constructed using only the same amount of data as the model's training budget, would it still provide meaningful improvements?
  • How would directly training on more raw data compare with using TMG? What are the actual benefits of TMG in terms of training cost and final model performance?

The current experiments mainly demonstrate that additional corpus statistics can improve training, but they do not sufficiently establish that TMG is an efficient way to utilize this extra information. This limitation directly affects the paper's central claim of data-efficient pretraining.

  1. Limited evaluation under sufficiently large training budgets.

The 3B model is trained on only 100M tokens, far below its compute-optimal training budget. Under such severely undertrained conditions, additional statistical information may be particularly beneficial. Although the authors evaluate Engram v1 under a full training budget for the 172M model, experiments with larger models trained closer to their compute-optimal budgets are still missing. This leaves the practical effectiveness of the proposed approach at scale unclear.

Overall Assessment

The paper presents an interesting idea and demonstrates measurable improvements in training efficiency. However, it does not sufficiently establish whether TMG provides meaningful benefits relative to the substantial amount of additional data used to construct it. I consider this a key missing evaluation needed to support the paper's central contribution.

Critical strengths

The paper addresses the important problem of improving pretraining efficiency.

Critical weaknesses
  1. Insufficient evaluation of how efficiently TMG utilizes the additional data.

This is my main concern. The paper constructs TMG using 350B tokens but evaluates its effectiveness primarily on models trained with only 100M tokens. In other words, TMG incorporates statistical information from a corpus approximately 3,500 times larger than the actual training data. Given this substantial amount of additional information, the observed improvements are not particularly surprising. However, it remains unclear how effectively TMG utilizes this information.

I believe two important questions need to be addressed:

  • If TMG is constructed using only the same amount of data as the model's training budget, would it still provide meaningful improvements?
  • How would directly training on more raw data compare with using TMG? What are the actual benefits of TMG in terms of training cost and final model performance?

The current experiments mainly demonstrate that additional corpus statistics can improve training, but they do not sufficiently establish that TMG is an efficient way to utilize this extra information. This limitation directly affects the paper's central claim of data-efficient pretraining.

Questions for authors

Please refer to the weaknesses.

Reviewer_ka3POpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The authors propose an auxiliary loss based on bigram statistics, where the auxiliary loss itself is a weighted KL divergence between a modified bigram distribution and the LM’s predictions, annealed over training. Many weighting schemes are considered, including weights based on the entropy of each token’s successor distribution, a curvature-inspired bottleneck score, inverse token frequency, and a learned gate. An architecture change that injects weighted next-token embeddings is also considered. The results show that there is a reduction in the number of pretraining tokens required to reach the same loss across multiple seeds for a 172M parameter LM and that there is more rapid convergence during the early part of training.

Critical strengths

The problem that the authors are studying, namely improving token efficiency during pretraining, is a very relevant one today, when LLM training costs are exorbitant and compute is scarce. The reporting on the experimental outcomes is detailed, and includes multiple runs on different seeds and various negative findings alongside the positive ones.

Critical weaknesses

I am not convinced of the novelty of the contribution, and relevant citations are missing. The idea of using n-gram statistics to help model training has been studied extensively in the past (e.g., "Using Large Corpus N-gram Statistics to Improve Recurrent Neural Language Models", Yang et al., 2019). More generally, the idea of using a smaller LM's output probabilities as part of the loss was studied under the name of 'reverse distillation' in 'Scaling Language Models: Methods, Analysis & Insights from Training Gopher' (Rae et al., 2022), where the authors found that the faster improvement occurs in the early part of training, but minimal gains were found once the model was allowed to finish the full training run.

The findings from prior work also change the interpretation of the experimental results. For example, Fig. 4 asserts a speedup versus baseline after only 100M tokens of pretraining for a 3B model. Given what we know from the Gopher work and since 100M tokens isn't enough to have converged under Chinchilla scaling, we can't conclude that there is a benefit for larger models from a plot that stops at just 100M tokens, since the early speedup might disappear completely when the training run is allowed to finish. For reference, the FineWeb paper trained a 1.71B model on 28B tokens under Chinchilla scaling, which is why I doubt that the early behavior after 100M tokens is informative.

The primary experimental results in Table 1 and Fig. 3 are based on a tiny 172M parameter model, which is so small that the vast majority of its parameters (>70%) are devoted to its vocab embedding layers rather than to the layers of the model itself. I don't think we can extrapolate from this to modern LLMs, which are significantly larger and not as dominated by the embedding matrices alone.

Questions for authors

Does the auxiliary loss ever improve model performance over a full training run? Fig. 3 shows that engram v1 produces an improvement, but engram v1 is an architectural change similar to the Deepseek Engram work, not a change to the loss, and the TMG loss is presented as a major contribution. In fact, Table 12 shows that the curvature-weighted loss performs worse than the baseline, which makes the TMG loss actively harmful.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.