Skip to content
AI News HubLIVE
Original source2 min read

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

Summary

The paper disproves the analogy between LLM token count and classical time complexity, introduces LLM Complexity—a metric based on the area under the accuracy-token curve—and shows it yields consistent task difficulty rankings across models, enabling an easy-to-hard curriculum that improves fine-tuning accuracy while reducing token usage.

SourcearXiv Computational LinguisticsAuthor: Yu-Hung Wu, Shao-Xiang Yuan, Chan-Hung Yu, Zih-Ching Chen, Kuan-Hao Huang, Shao-Hua Sun
LLM Complexity: Towards a Computational Complexity View of Large Language Model Inference
Report an error

The correction channel is not available yet. You can copy the article reference below for later.

Correction instructions
Read article

[Submitted on 19 Oct 2026]

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

View a PDF of the paper titled LLM Complexity: Towards a Computational Complexity View of Large Language Model Inference, by Yu-Hung Wu and 5 other authors

View PDF HTML (experimental)

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.

Comments: 10 pages, 20 with Appendix

Subjects:

Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

Cite as: arXiv:2611.24943 [cs.CL]

(or arXiv:2611.24943v1 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2611.24943

arXiv-issued DOI via DataCite

Submission history

From: Yu-Hung Wu [view email] [v1] Mon, 19 Oct 2026 08:23:11 UTC (481 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled LLM Complexity: Towards a Computational Complexity View of Large Language Model Inference, by Yu-Hung Wu and 5 other authors

View PDF

HTML (experimental)

TeX Source

view license

Additional Features

Audio Summary

Current browse context:

cs.CL

new | recent | 2026-11

Change to browse by:

cs cs.AI cs.LG

References & Citations

SciX

Google Scholar

Semantic Scholar

Loading...

Data provided by:

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)

Related Papers

Recommenders and Search Tools

Link to Influence Flower

Influence Flower (What are Influence Flowers?)

Core recommender toggle

CORE Recommender (What is CORE?)

Author

Venue

Institution

Topic

About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

Key points and analysis

Article intelligence

EngineersAdvanced

Key points

  • Token usage during inference does not monotonically align with classical time complexity
  • LLM Complexity quantifies task difficulty via the area bounded by the accuracy-token curve
  • Diverse LLMs produce highly consistent task rankings under this metric
  • An easy-to-hard curriculum built from LLM Complexity improves SFT accuracy and reduces token consumption

Highlights and analysis are generated automatically and may contain errors. Check the original source.