LLM Complexity: A Computational Complexity Perspective on Large Language Model Inference
arXiv:2611.24943 [cs.CL] | Submitted 19 October 2026 | 10 pages, 20 with appendix
Authors: Yu-Hung Wu, Shao-Xiang Yuan, Chan-Hung Yu, Zih-Ching Chen, Kuan-Hao Huang, Shao-Hua Sun
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
Abstract
Computational complexity theory provides a principled framework for characterizing the efficiency of computational problems. Large Language Models (LLMs) can similarly be viewed as computational systems that execute a structured process of input, inference-time compute, and output. Within this framing, the number of generated tokens is 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 rooted in how LLMs actually allocate computation during inference.
To address this, 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.
Key Contributions
- Reframing LLMs as computational systems. The paper treats inference as a structured process of input, inference-time compute, and output, with generated token count as an observable proxy for compute.
- Challenging the token-length/time-complexity analogy. The authors disprove the hypothesis that token usage aligns monotonically with classical time complexity, revealing a fundamental divergence in how LLMs allocate computation.
- Introducing LLM Complexity. A new metric that quantifies problem difficulty from the model's perspective using the area under the accuracy–token curve.
- Cross-model consistency. Diverse LLMs produce highly consistent task rankings under LLM Complexity, suggesting the metric captures stable, model-agnostic notions of difficulty.
- Practical application. An easy-to-hard curriculum built from LLM Complexity improves supervised fine-tuning accuracy while reducing token consumption.
- Real-world generalization. LLM Complexity yields more stable cross-model correlations than human-annotated difficulty labels on real-world tasks.
Relevance in 2026
As inference-time compute (e.g., extended reasoning, chain-of-thought, and test-time scaling) becomes a central lever for LLM performance, understanding how models allocate computation—rather than merely how much they emit—is increasingly critical for efficiency, benchmarking, and training. This work contributes a complexity-theoretic lens to that effort, offering a model-grounded difficulty metric with direct implications for data curation and curriculum design.
Cite as: arXiv:2611.24943 [cs.CL] | DOI: https://doi.org/10.48550/arXiv.2611.24943
via ArXiv CL+LG
