The Hardness of Estimating Cross-Entropy Risk for Language Models

arXiv:2608.15798 · cs.LG, stat.ML · Submitted 2026-08-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The Hardness of Estimating Cross-Entropy Risk for Language Models".

Jane: Here's the gist of the paper. Language models are compared by their held-out per-token cross-entropy risk—the quantity scaling laws are fitted to.

Tom: This paper shows that it cannot be consistently estimated.

Jane: Impossibility of Consistent Estimation The per-token cross-entropy risk is hard to estimate because of a topological fact: among the possible states, finite risk and infinite risk each lie arbitrarily close to every instance of the other.

Tom: Consequently no estimator—not merely the holdout average—is consistent at every state at which the risk is defined.

Title and authors: Tom: Let's look at the title again, "The Hardness of Estimating Cross-Entropy Risk for Language Models." It sounds like they’re setting up a really tough problem right out there. The authors are Hanti Lin from UC Davis.

Jane: Hanti Lin is a researcher, and this paper tackles the fundamental difficulty in estimating that per-token cross-entropy risk that we use so often in model evaluation. What does it mean when they say it's hard to estimate consistently?

Lu: It means you can't find a single estimator—not just the simple holdout average we’re used to—that converges to the true risk for every possible data distribution and model pair. Consistency is defined relative to a specific state of the world, which is a data-generating distribution paired with the model you actually train.

Meng: So they are saying that even if we use a method that looks good on some test sets, it can't reliably predict the true risk across all possible scenarios because those scenarios are just too close together topologically.

Lalam: That’s a deep statement about the nature of what we can actually measure when dealing with infinite sequence spaces and softmax parameters. It points to a limit on statistical estimation itself for this specific quantity.

Tom: And they make it clear that this difficulty isn't just theoretical; it persists even when you impose practical constraints, like limiting the expected length of the sequences or restricting us only to models that use full support during training.

Jane: That persistence is what’s really worrying for practitioners, because we always try to build our methods around those assumptions. If it fails even under those restrictions, it makes us rethink how we're approaching model quality assessment entirely.

Lu: The paper argues that the failures of consistency aren't isolated spots on a map; they are dense across the entire restricted class of models and data-generating mechanisms, which is what Theorem three proves.

Meng: That density means there’s no safe neighborhood we can assume is reliable for our risk estimation procedures, which makes deploying these models much more cautious when relying on this metric.

Lalam: It sounds like the paper isn't just saying "our method is weak"; it's saying that the quantity itself has inherent properties that make it fundamentally unestimable consistently under standard settings.

The paper's summary: Tom: So, what’s the actual substance of this "Hardness of Estimating Cross-Entropy Risk for Language Models" paper? It boils down to showing that no estimator works consistently across all possible states because finite and infinite risk are too close together.

Jane: They quantify the per-token cross-entropy risk, which is what we use to decide which model checkpoint ships or how good it is reported as a summary of quality, but they show this estimation procedure cannot converge to the true risk for every possible pair of data distribution and trained model.

Lu: The authors focus on quantifying over both the models themselves and the data-generating mechanisms, because what matters—what decides if a model’s risk is estimable—is a property of that distribution that no single sample can ever reveal.

Meng: So, the problem isn't just about having too little data; it’s about this deep statistical structure where the true risk might be infinite even though our training process seems to suggest it should be finite.

Lalam: They explicitly point out that because the space of token sequences is countably infinite and a language model assigns positive probability to every sequence in its softmax parameterization, the risk is an infinite sum of non-negative terms that can diverge.

Tom: That’s a crucial technical detail—the divergence potential—that undermines the simple idea that we can just rely on the law of large numbers for convergence when the risk itself isn't guaranteed to be finite.

Jane: It shifts our focus from just finding a better estimator to recognizing that we might need to change what we are even trying to estimate, because estimating this specific quantity consistently seems impossible under the current framework.

Lu: The paper makes this impossibility theorem, along with a refinement of pointwise consistency defined over possible states of the world, which captures how risk is supposed to be measured relative to a specific setup (p, q).

Meng: So they’re not just saying "this metric is hard"; they are defining *why* it's hard by showing the underlying topology of the space where risk lives.

The paper's improvements: Tom: Okay, so if the problem is impossible in general, what are these papers suggesting we can actually do about it? They propose two ways out, which they call ways out for estimation.

Jane: They suggest one way out involves using a bounded context window. If you floor the model’s next-token probabilities with a window size, the risk becomes finite exactly when the data-generating distribution has a finite expected sequence length.

Lu: That’s interesting because it provides a statistical justification for something we might already do computationally—bounding the sequence length—and it allows for consistent estimation under that new assumption about bounded expected sequence length.

Meng: So if we cap the context window, you get a finite risk estimate, but only if you can guarantee that the actual data sequences won't be longer than what you capped at. That puts a constraint on our deployment assumptions.

Lalam: It’s a practical trade-off: we gain consistency under the assumption of finite length by imposing that length limit on the model itself.

Tom: Then there’s the second way out, which is reporting risk only when it falls below a threshold you set beforehand. This restores consistency at every state except for those exact points where the true risk equals your fixed threshold r.

Jane: So, if we only report a risk score when it's below some pre-set level, we restore consistency—but we have to accept that the goal of estimation has changed; you’re not trying to find the absolute truth anymore.

Lu: That shift in goal is key. Instead of aiming for perfect accuracy across all states, you are aiming for consistency within a defined bound r. This means model selection becomes about whether it passes a certain practical hurdle, rather than finding the perfect risk value.

Meng: So if we use that threshold method, it basically means we only care if the model is *good enough* according to our predefined safety or performance standard, not if it has the mathematically perfect cross-entropy score.

Conclusion: Tom: So to wrap up this discussion on "The Hardness of Estimating Cross-Entropy Risk for Language Models," we’ve established that consistently estimating per-token cross-entropy risk is fundamentally impossible under standard settings because finite and infinite risk are too close together topologically.

Jane: The paper shows this impossibility even when we restrict our analysis to models with full support, proving the failures of consistency are dense everywhere in the restricted class of possibilities.

Lu: The main contribution is providing this impossibility theorem, along with that refinement of pointwise consistency over possible states of the world, which helps us understand exactly where statistical estimation breaks down.

Meng: For deployment, this means we have to be very careful about what metrics we rely on; simply calculating a risk score and trusting it as the absolute measure is risky because there’s always a hidden state where our estimate could be wildly off.

Lalam: The ways out are interesting—either bounding the context window to enforce finite length, or using a fixed reporting threshold r which trades absolute accuracy for guaranteed consistency within that bound.

Tom: Both routes point toward a necessary revision of what we consider an acceptable risk estimation procedure for pretraining, because the original idea of finding a single perfect number seems out of reach.

Jane: It’s clear that the future research needs to focus on these new constraints—like sequence length limits or threshold-based reporting—to make sense of how we actually use this risk information in practice.

Lu: I think the next step is exploring how these bounded procedures integrate into larger, more complex learning paradigms, seeing if they can offer meaningful control over model behavior.

Meng: From an engineering standpoint, it’s good that someone has mapped out the exact limits of what we can reliably measure before we waste time chasing an unattainable perfect number.

Lalam: It's a big paper because it tells us exactly where our current statistical toolkit stops working for this specific type of risk calculation.

Hanti Lin

University of California, Davis

cs.LG, stat.ML

Submitted: 2026-08-16

Updated: 2026-10-30

Comments: Substantially revised and expanded version under a new title. Retains the main impossibility results of v1 and adds a new positive theorem concerning Transformers, which prompted a thorough overhaul of the paper's motivation, organization, and discussion of its significance

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 78/100

The gist: Language models are compared by their held-out per-token cross-entropy risk—the quantity scaling laws are fitted to.

Key concepts

Per-token cross-entropy risk
This is the metric used to compare language models by measuring how well they predict the next token at each step. The paper shows this specific measure cannot be reliably estimated consistently across all possible model and data scenarios.
Estimation consistency
Consistency means that an estimation procedure yields a reliable result regardless of the true underlying data distribution or model being used. The paper demonstrates that no single estimation method can achieve this consistency for cross-entropy risk under standard assumptions.
Bounded context window
Limiting the model's lookahead to a fixed, finite sequence length forces the risk to be finite if the true data has a finite expected sequence length. This provides a statistical justification for using bounded windows in estimation procedures.
Screened reporting procedure
Instead of providing an exact risk estimate, this method reports only when the calculated risk is below a predetermined threshold 'r'. This approach restores consistency by ensuring that if all candidates are worse than 'r', the result is consistently reported as hopeless.

Terminology

Summary

Language models are compared by their held-out per-token cross-entropy risk—the quantity scaling laws are fitted to. p. 0

Where the paper says it

Cross-Entropy Risk Estimation for Language Models: Inconsistency Must Be Dense, and the Holdout Method Is No Exception Hanti Lin University of California, Davis ika@ucdavis. edu Abstract Language models are compared by their held-out per-token cross-entropy risk— the quantity scaling laws are fitted to.

This paper shows that it cannot be consistently estimated. p. 0
Where the paper says it

edu Abstract Language models are compared by their held-out per-token cross-entropy risk— the quantity scaling laws are fitted to. We show that it cannot be consistently estimated.

Impossibility of Consistent Estimation

The per-token cross-entropy risk is hard to estimate because of a topological fact: among the possible states, finite risk and infinite risk each lie arbitrarily close to every instance of the other. Consequently no estimator—not merely the holdout average—is consistent at every state at which the risk is defined. p. 0

Where the paper says it

The per-token cross-entropy risk is hard to estimate because of a topological fact: among the possible states, finite risk and infinite risk each lie arbitrarily close to every instance of the other. Consequently no estimator—not merely the holdout average—is consistent at every state at which the risk is defined.

Worse, inconsistent estimation persists under both bounding the expected sequence length and restricting to full-support models; and in that restricted setting the states at which inconsistency occurs are even dense. p. 0
Where the paper says it

Consequently no estimator—not merely the holdout average—is consistent at every state at which the risk is defined. Worse, inconsistent estimation persists under both bounding the expected sequence length and restricting to full-support models; and in that restricted setting the states at which inconsistency occurs are even dense.

Theorem 3 says that on that same restricted class the failures of consistency are not isolated but dense: no matter which state one takes as a working hypothesis, and no matter how small a neighborhood of it one is willing to assume the truth lies in, that neighborhood contains a state at which the estimator fails. p. 2
Where the paper says it

to models of full support (a consequence of the common practice of softmax normalization). Theorem 3 says that on that same restricted class the failures of consistency are not isolated but dense: no matter which state one takes as a working hypothesis, and no matter how small a neighborhood of it one is willing to assume the truth lies in, that neighborhood contains a state at which the estimator fails.

Defining Consistency and States of the World

Estimation consistency is defined relative to a possible state of the world: a pair consisting of a data-generating distribution and a model we turn out to train. Defining pointwise consistency by quantifying over models q as well as the data-generating mechanism p is important. p. 1

Where the paper says it

So, estimation consistency—namely, stochastic convergence to the true estimand—is naturally a property of an estimator at a pair (p, q), which is a state of the world in which the data generation is one thing and the model we happen to have trained is another. Defining pointwise consistency by quantifying over models q as well as the data-generating mechanism p is important.

The results show that no estimation procedure settles the question, and they say it three times over, each time on a smaller class of possibilities. p. 1
Where the paper says it

We have limited mathematical knowledge about the distribution induced by the trained model—about the exact identity of the trained model. Our main results say that no estimation procedure settles the question, and they say it three times over, each time on a smaller class of possibilities.

Ways Out for Estimation

Two interesting ways out are identified, and neither is free. Way out 1: using a bounded context window, we can floor a model’s next-token probabilities, making its risk finite exactly when the data-generating distribution has finite expected sequence length—a new, statistical rationale for a choice that was made on computational grounds. p. 0

Where the paper says it

Two interesting ways out are identified, and neither is free. Way out 1: using a bounded context window, we can floor a model’s next-token probabilities, making its risk finite exactly when the data-generating distribution has finite expected sequence length—a new, statistical rationale for a choice that was made on computational grounds, though the assumption it substitutes is itself beyond the reach of any test.

Way out 2: reporting the risk only when it falls below a threshold fixed in advance restores consistency, at no cost to what model selection actually requires—but we need to recognize that the goal of estimation is revised. p. 0
Where the paper says it

Way out 1: using a bounded context window, we can floor a model’s next-token probabilities, making its risk finite exactly when the data-generating distribution has finite expected sequence length—a new, statistical rationale for a choice that was made on computational grounds, though the assumption it substitutes is itself beyond the reach of any test. Way out 2: reporting the risk only when it falls below a threshold fixed in advance restores consistency, at no cost to what model selection actually requires—but we need to recognize that the goal of estimation is revised.

Restricting Model and Data Classes

The impossibility result earns its keep by showing where the possibilities lie. The main result can be restated as a list of conditions that cannot all hold together, each of them a candidate for abandonment. For example, C.1 Sequence Space suggests bounding the length of a sequence at some N and X becomes finite. p. 1

Where the paper says it

Theorem 1 says that no estimator is consistent at every state at which the estimand exists, be it finite or infinite. Theorem 2 says that this survives two natural restrictions at once—bounding the expected sequence length by a constant fixed in advance, and confining attention 2

Restricting the Estimand

The second exit involves restricting what is to be estimated by fixing a real-valued threshold r in advance. The screened procedure is thus consistent at every state except those with ρ(p, q) = r exactly, where it may vacillate forever—the standard price of a threshold fixed in advance. p. 2

Where the paper says it

• Way out 2: An alternative estimand that is good enough. If what needs to be known is just the true risk when it falls below a threshold r fixed in advance, and otherwise we only need to know that it is at least r (be it finite or infinite), then this screened estimand can be consistently estimated at every stated where the risk is defined, and nothing beyond the law of large numbers is needed to see this.

Relocating Presupposition

Flooring the model restores consistency too, and the finite context window supplies the floor as a byproduct of a choice made on entirely computational grounds. The floor relocates the unanswerable question. p. 0

Where the paper says it

Two interesting ways out are identified, and neither is free. Way out 1: using a bounded context window, we can floor a model’s next-token probabilities, making its risk finite exactly when the data-generating distribution has finite expected sequence length—a new, statistical rationale for a choice that was made on computational grounds, though the assumption it substitutes is itself beyond the reach of any test.

Estimation Error Redefinition

The measure of error Error of Section 4 is what makes an estimate of a finite number infinitely wrong when the risk is in fact infinite. To speak of f(x) as the error of an estimate is to speak of the distance between the estimate and the quantity being estimated. p. 7

Where the paper says it

[0, ∞] of a quantity v ∈ [0,∞] is Error(u, v) :=    |u − v|, if u and v are both finite, ∞, if exactly one of u and v is infinite, 0, otherwise, both being infinite. The second clause carries the content: a finite estimate of an infinite quantity is not merely very wrong but infinitely so, which forces an estimator succeeding where the risk is infinite to certify the infinitude by returning ∞ itself.

Comparison Over Absolute Risk

The difference is well-defined only when at least one of the two risks is finite; if both are infinite it is the undefined ∞ − ∞, and by Theorem 1 no procedure determines which case obtains.

Conclusion on Methodology

The algorithm actually in use has two stages: empirical risk minimization on training data, and then model selection by risk estimation on held-out data. Flooring a minimization-trained model is one route to consistent estimation (Section 5. p. 9

Where the paper says it

One might think the q argument superfluous on the ground that the model is not unknown—we trained it, we hold every weight. But what decides whether its risk can be estimated, as the theorems above and Section 5.

1), and, when the window is at least the training length, a route that costs nothing in empirical risk—so that minimization is not compromised but extended. p. 3
Where the paper says it

A statistical theory of risk estimation is therefore an important part of a learning theory for pretraining—and the two ways out above are what allow the second stage to run at all. The first supplies an estimate to sift by: a bounded context window returns, at no cost in empirical risk when the window is at least the training length, a minimizer whose per-token risk can be consistently estimated.

Either suffices to escape the impossibility result of this paper, and both point to the importance of risk estimation for a statistical learning theory of pretraining. p. 3
Where the paper says it

The two stages together constitute the learning algorithm, and the second of them relies on risk estimation. A statistical theory of risk estimation is therefore an important part of a learning theory for pretraining—and the two ways out above are what allow the second stage to run at all.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Bounded context window implementation for risk estimation can be used to floor a model’s next-token probabilities, making its risk finite exactly when the data-generating distribution has finite expected sequence length. This allows for consistent estimation of per-token cross-entropy risk under the assumption of a bounded expected sequence length.

  2. A screened reporting procedure can be implemented where only the true risk below a fixed threshold r is reported, and otherwise only that the risk is at least r, restoring consistency at every state except those with exactly rho equals r. This supports model selection by returning nothing at all if every candidate is declared hopeless.

  3. Model training can be extended to include a two-stage procedure where the second stage relies on risk estimation for model selection. This stage can use a bounded context window to return an empirical risk minimizer whose risk one can afterward come to estimate with the held-out data, costs nothing in empirical risk when the window is at least the training length.

Abstract

Language models, once pretrained, are routinely assessed by the holdout method, which estimates their per-token cross-entropy risk---a quantity that may be finite or infinite. We prove possibility and impossibility theorems that characterize the hardness of this estimation problem. The estimand depends on two objects: the unknown data distribution p and the distribution q induced by the language model under study. Our ignorance of p is empirical, whereas our ignorance of q, or at least of its tail, is mathematical; so the parameter space should range over pairs (p,q) ---a product space---to fully capture our ignorance. Negative results: no estimator is pointwise consistent, even when the parameter space is restricted to full-support models and to data distributions whose expected text length is below a fixed bound; worse, every estimator fails on a dense set of pairs. Positive results: the holdout estimator becomes pointwise consistent when the models are further restricted to Transformers or, architecture-neutrally, to full-support models with a finite context window; and, where no such design is in place, it still consistently estimates the risk capped at any fixed threshold, which suffices for screening candidate models in practice. Lesson: designs such as the Transformer architecture and finite context windows, although adopted for computational or engineering reasons, pay a statistical dividend: they suffice to make pointwise consistency possible---a dividend visible only in how they turn a negative result into positive ones.

Sources

Related papers