- 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:
-
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.
-
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?
-
a typo in Table 4, the first entry's Method is misspelled as "Pre-traine"
-
Are the Time, Length, and Budget scores normalized before being used in the sampling weights? These metrics have different unit scales, whereas the proposed metric lies only in . Given the temperature schedule introduced, without appropriate normalization it could possibly give different sampling concentrations and undermine the fairness of this comparison.
-
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.
-
Section 6.1, the sentence "Smaller concentrates ..., while larger produces ..." appears identically twice in the same paragraph.