acceptodds
Withdrawn from ICLR 2027

LLM Complexity: Towards a Computational Complexity View of Large Language Model Inference

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Computational complexity theory offers a principled framework for characterizing the efficiency of computational problems, and Large Language Models (LLMs) can similarly be viewed as computational systems executing a structured process of input, inference-time compute, and output. In this context, the number of generated tokens emerges as a natural and directly observable proxy for inference-time compute. However, we show that the tempting analogy between LLM token length and classical time complexity does not hold. We disprove the hypothesis that inference-time token usage aligns monotonically with classical time complexity, demonstrating a fundamental divergence grounded in how LLMs actually allocate computation during inference. To this end, we introduce LLM Complexity, a new metric designed to quantify problem complexity from the perspective of LLMs by characterizing the area bounded above by the accuracy–token curve. We find that diverse LLMs induce highly consistent task rankings under LLM Complexity, indicating that the metric captures stable notions of difficulty across models. We leverage this property to construct an easy-to-hard curriculum for supervised fine-tuning, which improves accuracy while reducing token consumption. Finally, we demonstrate that LLM Complexity generalizes to real-world tasks, producing more stable cross-model correlations than human-annotated difficulty labels.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Computational Complexity

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_KbH1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors provide an empirical perspective that when using LLMs for solving algorithmic tasks, classical computational complexity does not align well with reasoning token usage. They propose a "LLM Complexity" which measures how quickly the accuracy improves with expending more token budget. This is defined quite intuitively, since for more difficult tasks, LLMs cannot answer it correctly without sufficient reasoning tokens, therefore higher complexity. The authors implement this metric by truncating a long reasoning trace at different token budgets and forcing the model to give answer directly from each partial trace.

They evaluate the metric on various algorithmic tasks across problem sizes and LLMs, and compare complexity rankings across models and prompt variants. They further use the metric to construct curriculum for supervised fine-tuning, and evaluate the metric with additional real-world reasoning settings.

Critical strengths

The paper is generally clear and easy to follow. The empirical perspective on the relationship between task difficulty and reasoning tokens is quite interesting. The proposed curve-based metric is indeed more informative than naive metrics like simple token length or peak accuracy. The authors did sufficient experiments across models with scales from 20B to 253B to demonstrate their story.

Critical weaknesses

About framing this work as "LLM complexity"

I have been thinking about this on and off for several days, and I still feel that calling this proposed metric "complexity" is quite misleading for audience to understand the core contribution of this paper. The term "computational complexity" is more commonly used to describe resources used to run (a class of) algorithms, but the metric proposed here actually measures an ambiguous mixture of task difficulty and model capability. It does not distinguish cases where model needs more computation to solve the task (a flatter curve) from cases where the model completes a task quickly but performs poorly (a steeper curve but lower peak value). The authors has already described their metric as model sensitive and as an operational notion, but did not separate well these two cases and often misuse the former one to blur the distinction between.

The proposed metric fails to identify the most critical factor for guiding actual allocation of compute resources, which is a key role that computational complexity should play. It cannot directly tell which tasks would benefit from more compute, and to what extent. Does higher "LLM complexity" on a model and a task imply that more computation should be allocated, or does it suggest that further computation is not worth the effort? Given how this metric is described in the paper, one may easily construct curves with the same normalized log-budget AUC but one such curve might climb while another is completely flat and cannot benefit at all from allocating more resources. If it cannot distinguish between these two scenarios, then what is its value for decision-making as an indicator of computational demand?

Additionally, different model (especially models at different scales) might allocate task-solving capabilities into different amount of implicit computations that happens on internal circuits cross-layer cross-token and explicit context-based token reasonings. Increasing model depth and CoT steps can provide different computational capabilities, which has been well-examined in [1,2] and various mech interp studies. Hence, fewer reasoning tokens may reflect computation already performed internally, rather than lower computational difficulty, which is a limitation for all metrics based only on explicit token expense.

Different ways to input the task and to continue generating results based on the truncated reasoning traces might also affect the final results. The evaluation in this paper does not distinguish well "answerability" from budget-constrained performance. Since the curve is constructed from nested truncated prefixies of a single long trajectory, this does not directly characterize performance from independently allocated reasoning budgets at that length. The authors need to provide further clarification in detail about the effect here by comparing natively-sampled reasoning traces with different lengths from the truncated ones, and how subsequent answer generation tokens count toward the budget.

About novelty and missing related work

Given that I find the perspective of defining this metric as "complexity" insufficiently justified, the remaining novelty aspects of this paper is not well-established. [3] has already proposed studying tradeoffs between reasoning accuracy and token lengths, and [4] has examined progressively truncating reasoning traces and aggregating performance using AUC. The authors did not elaborate their contribution well beyond these existing approaches, which have already been recognized through their citations and conference records.

References

[1] Nikankin, Y., Reusch, A., Mueller, A., & Belinkov, Y. (2025, May). Arithmetic without algorithms: Language models solve math with a bag of heuristics. In International Conference on Learning Representations (Vol. 2025, pp. 55939-55965). https://arxiv.org/pdf/2410.21272

[2] Yehudai, G., Amsel, N., & Bruna, J. (2026). Compositional reasoning with transformers, rnns, and chain of thought. Advances in Neural Information Processing Systems, 38, 54567-54599. https://arxiv.org/pdf/2503.01544v1

[3] Lee, A., Che, E., & Peng, T. (2025). How well do llms compress their own chain-of-thought? a token complexity approach. https://arxiv.org/pdf/2503.01141

[4] Wang, X., Joshi, N., Plank, B., Angell, R., & He, H. (2026, April). Is it thinking or cheating? detecting implicit reward hacking by measuring reasoning effort. In International Conference on Learning Representations (Vol. 2026, pp. 96956-96981). https://arxiv.org/pdf/2510.01367

Questions for authors

Please address the major concerns listed above in Critical Weaknesses. I also have several minor presentation concerns:

  1. In Table 2 the caption claims "... LLM Complexity yields the best cross-model correlation among all the other heuristic complexity definitions.", however its average Spearman correlation is actually lower than Length.

  2. In caption of Table 4 "... LLM Complexity achieves the highest average accuracy and lowest average token usage, ..." This table does not report any token usage statistics but only accuracies. Where are the measurements supporting this claim?

  3. a typo in Table 4, the first entry's Method is misspelled as "Pre-traine"

  4. Are the Time, Length, and Budget scores normalized before being used in the P∝exp⁡(−C/τ)P \propto \exp(-\mathcal{C}/\tau) sampling weights? These metrics have different unit scales, whereas the proposed metric lies only in [0,1][0,1]. Given the temperature schedule introduced, without appropriate normalization it could possibly give different sampling concentrations and undermine the fairness of this comparison.

  5. Figure 4 in appendix distinguishes seen/unseen algorithm families and instances used for training, but Table 4 only gives "seen/unseen". Should provide more details here.

  6. Section 6.1, the sentence "Smaller τ\tau concentrates ..., while larger τ\tau produces ..." appears identically twice in the same paragraph.

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

The paper shows that the number of tokens generated by an LLM does not correlate with the task complexity on 12 classic algorithmic tasks. This is motivated by the widespread intuition that the number of generated tokens is analogous to the number of time steps of an algorithm. The authors propose a new metric for assessing a task's complexity, which they call LLM complexity. This new metric captures how the accuracy improves as a function of the number of allowed tokens. The authors show this is a useful metric by checking whether the models rank tasks consistently using this metric, by showing that LLM complexity is robust to changes in the prompt, and by using it successfully for a curriculum.

Critical strengths
  1. The paper is very clear and easy to follow, and seems mostly human-written (this is a big plus, since text edited with LLMs tends to become harder to read). The authors explain all relevant concepts in the right amount of detail.
  2. The proposed metric seems genuinely new and interesting and has some useful applications, such as curriculum learning. With the right framing (see below), I think this could be a strong paper.
Critical weaknesses
  1. I find the motivation of the paper, i.e., the analogy between the number of tokens and time complexity in complexity theory, quite unconvincing and not new, despite being framed as such.

First, it is true that many theoretical studies of transformers show that they are Turing complete, under various assumptions. However, all such studies work with an idealized transformer that is not used in practice. For instance, Perez et al. (2021) assume unbounded numerical precision and a non-standard attention mechanism and positional encodings. I believe Jiang et al. (2026) use a more realistic version of transformers, but there are still differences. In any case, all these papers prove that there exist parameter settings under which the transformer is Turing complete, not that they can be found during standard training with gradient descent. Even if transformers with chain-of-thought were Turing complete, I'm not sure what can be said about the number of tokens they generate at inference time. For instance, there is no reason to believe they would necessarily implement the most efficient algorithm for a task. For this reason, I find the finding that the number of tokens does not match the problem complexity rather unsurprising. I understand that, given the current state of the field, there is no clear connection between LLMs used in practice and classic complexity theory, but I believe the discussion should be made more precise.

Second, the finding is not new. I'm not familiar with all the recent relevant literature, but here are some other papers that show, in my opinion, something similar.

  • Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity. 2025. Vardhan Palod, Karthik Valmeekam, Kaya Stechly, Subbarao Kambhampati.
  • The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity. 2025. Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, Mehrdad Farajtabar.
  • Rethinking the Illusion of Thinking. 2025. Iñaki Dellibarda Varela, Pablo Romero-Sorozabal, Eduardo Rocon, Manuel Cebrian.
  • Between Underthinking and Overthinking: An Empirical Study of Reasoning Length and correctness in LLMs. 2025. Jinyan Su, Jennifer Healey, Preslav Nakov, Claire Cardie.

Additionally, there are papers showing that longer chains are not necessarily better:

  • The relationship between reasoning and performance in large language models—o3 (mini) thinks harder, not longer. 2025. Marthe Ballon, Andres Algaba, Vincent Ginis.
  • Don't Overthink it. Preferring Shorter Thinking Chains for Improved LLM Reasoning. 2026. Michael Hassid, Gabriel Synnaeve, Yossi Adi, Roy Schwartz.

I encourage the authors to position their work better relative to related work. On a similar note, I find the title misleading. The point is that there is no clear connection between LLM inference and computational complexity, and the paper does not advance our understanding of this. In fact, it argues for a completely different metric.

  1. To assess whether there is any connection with complexity theory, we must be able to somehow analyze the behaviour of the models in the limit. This is of course not possible empirically, but the sizes of the problems tested seem quite low. If I understand correctly, the authors test tasks of size at most 100.

  2. One of the desiderata for the new metric is cross-model agreement. But to assess this properly, the models should be sufficiently diverse, otherwise the metric might not be transferable to a different model. Could the authors comment on the choice of the models?

  3. Given the above, I'm not sure why the new metric is needed. It seems like the strongest motivation is the curriculum learning application. But even there, the experiments seem unconvincing. The authors seem to compare their metric only with toy curricula and no state-of-the-art methods.

  4. Minor: The authors often use \citet{..} instead of \citep{..} and vice versa. There are also some typos ("Pre-traine" in line 333, "models" line 106, "establishes" line 107, etc.).

Questions for authors

See my questions above. Also:

  1. Why is it reasonable to prompt the model again, once it has stopped, to force it to produce more tokens artificially?
  2. Did you think about how this metric could be computed when the task has no ground-truth answers? Even in the "real-world" tasks like DeepMath and RuleArena, answers are provided.
Reviewer_5mzdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether LLM inference-time token usage aligns monotonically with the worst-case time complexity of classical algorithmic tasks. Through experiments involving five open-weight LLMs and twelve algorithmic problems, the authors observe discrepancies between algorithmic complexity rankings and model token consumption. They introduce LLM Complexity, defined as one minus the normalized area under the accuracy–token-budget curve in log-budget space. The experiments assess the consistency of the resulting difficulty rankings across models and prompt variants. The authors further explore the metric’s practical utility through curriculum-based supervised fine-tuning and extend their evaluation to DeepMath and RuleArena.

Critical strengths
  1. An informative perspective on inference-time task difficulty. The paper highlights that classical worst-case algorithmic complexity alone does not adequately characterize the token consumption of the evaluated LLMs. Its observations concerning task structure and output requirements provide a useful starting point for understanding the factors that influence inference behavior.

  2. Empirical evaluation beyond proposing a metric. The authors investigate cross-model consistency and prompt robustness and explore a downstream application through curriculum learning. The generally consistent rankings across the evaluated settings suggest that the metric captures a reproducible empirical signal, while the fine-tuning experiment provides initial evidence of practical utility.

Critical weaknesses
  1. The computational interpretation of the metric requires further validation. The score aggregates accuracy across budgets and may therefore reflect several factors beyond computational difficulty, including model capability, output requirements, formatting compliance, and sensitivity to the prefix-truncation procedure. Comparing finite-sample model behavior with asymptotic worst-case algorithmic bounds does not, by itself, establish the proposed computational interpretation. Although the paper includes an answer-format prompt variation, this does not directly distinguish substantive reasoning errors from formatting or parsing failures. Similarly, the evaluation does not establish whether low-budget performance primarily reflects insufficient computation or sensitivity to the truncation intervention. Addressing these issues would help clarify what the metric measures and strengthen its interpretation and measurement validity.

  2. The additional evaluation cost is not sufficiently justified by the demonstrated incremental benefit. Computing LLM Complexity requires answer generation and evaluation at multiple budgets between 1,000 and 16,000 tokens. Although a single long reasoning trace is reused, the repeated answer-stage evaluations—up to 16 budget evaluations per instance—introduce additional inference and evaluation costs relative to computing Length from a single generated trace. However, in Table 2, Length achieves slightly higher average Spearman correlation than LLM Complexity (0.836 versus 0.834), while LLM Complexity achieves higher Kendall correlation (0.664 versus 0.650). These numerically close results leave the incremental benefit in this particular comparison unclear, especially without uncertainty estimates. Quantifying the trade-off between the additional computational cost and improvements in robustness would strengthen the paper’s contribution.

Questions for authors
  1. How are final answers parsed and checked? Are formatting or parsing failures counted as incorrect answers, and what proportion of errors do they account for at different budgets? Would the main ranking conclusions remain unchanged under format-tolerant parsing and task-specific correctness verification?

  2. How do you distinguish insufficient computation from sensitivity to prefix truncation? Could you provide a comparison with an alternative budget-control procedure to assess this concern? Please also clarify whether additional reasoning and answer-generation tokens produced after truncation are included in the reported budget.

  3. What are the actual costs of computing LLM Complexity relative to Length, measured in total generated tokens and inference time? Could you provide uncertainty estimates for the differences in Table 2 and assess whether evaluating fewer budget points preserves the reported benefits?

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

Related papers

Discussion (0)

Sign in to comment.