LLM Complexity: a new difficulty metric from the accuracy-token curve
The paper starts from an appealing analogy. Computational complexity theory gives a principled way to describe how efficient a problem is to solve, and an LLM can be seen as a computational system that takes an input, spends inference-time compute, and produces an output. On that view, the number of tokens a model generates looks like a natural, directly observable proxy for inference-time compute.
The authors then argue the analogy breaks. They say they disprove the hypothesis that inference-time token usage aligns monotonically with classical time complexity, and describe this as a fundamental divergence grounded in how LLMs actually allocate computation during inference.
To replace the broken analogy, they introduce LLM Complexity, a metric meant to quantify how complex a problem is from the LLM's own perspective. It is defined by characterizing the area bounded above by the accuracy-token curve, that is, how accuracy on a task relates to the number of tokens the model generates.
The authors report three findings about the metric. First, diverse LLMs induce highly consistent task rankings under LLM Complexity, which they read as evidence that it captures stable notions of difficulty across models. Second, they use that property to construct an easy-to-hard curriculum for supervised fine-tuning, which they say improves accuracy while reducing token consumption. Third, they say LLM Complexity generalizes to real-world tasks, where it produces more stable cross-model correlations than human-annotated difficulty labels.
Key facts
- The paper says the analogy between LLM token length and classical time complexity does not hold, and that token usage does not align monotonically with classical time complexity.
- It introduces LLM Complexity, a metric defined by the area bounded above by the accuracy-token curve, to measure problem difficulty from the LLM's perspective.
- Diverse LLMs produce highly consistent task rankings under the metric, which the authors take as a sign of stable notions of difficulty across models.
- An easy-to-hard supervised fine-tuning curriculum built on the metric is reported to improve accuracy while reducing token consumption.
- On real-world tasks, the authors say LLM Complexity gives more stable cross-model correlations than human-annotated difficulty labels.
Why it matters
Token count is the easiest thing to measure about a model's reasoning effort, so it is tempting to treat it like running time in classical complexity theory. The paper challenges that shortcut directly, claiming the two do not line up monotonically. If that holds, reading a long chain of thought as 'harder computation' is unreliable. The proposed alternative, LLM Complexity, ties difficulty to the accuracy-token curve instead of to token length alone, and is offered as a difficulty measure defined from the model's side rather than from the problem's formal class.
Who it affects
Researchers studying inference-time compute and reasoning length are the most direct audience, since the paper questions a common proxy. Teams that fine-tune models with supervised data are also addressed: the authors propose ordering training tasks from easy to hard using the metric. People who build benchmarks or label task difficulty by hand are touched too, because the paper says its metric yields more stable cross-model correlations than human-annotated difficulty labels.
How to use it
The paper's own use case is a curriculum for supervised fine-tuning: rank tasks by LLM Complexity, then train from easy to hard. The authors report this improves accuracy while reducing token consumption. The practical recipe rests on the metric's definition, the area bounded above by the accuracy-token curve. The source text mentions no code or data release, so a reader who wants to apply it would need to follow the full paper.
How solid is it
This is an arXiv preprint, and every result in the text is reported by the authors themselves. The abstract gives no numerical results: no accuracy gains, token reductions, correlation values, or sizes of the fine-tuning effect. The models, datasets, benchmarks and real-world tasks used are not named, and the abstract does not say which classical complexity classes or problems were compared against token usage. The claim of consistent rankings across diverse LLMs is the central support for the metric, but the evidence behind it cannot be judged from the abstract alone.
Risks and caveats
The strongest claims, that the analogy is disproved and that the curriculum improves accuracy while cutting tokens, come without figures or baselines in the available text, so their size and robustness are unknown. The abstract does not specify how much accuracy improved or how much token consumption fell under the curriculum, nor the baseline it is compared with. Consistent rankings across models show agreement on difficulty, which the authors interpret as stable difficulty; that is their reading of the result. Treat the work as an early, unreviewed proposal until the details and replications are available.
“we show that the tempting analogy between LLM token length and classical time complexity does not hold”
— From the paper's abstract, arXiv 2611.24943