Skip to content
OpenTrain AIFor AI Companies

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

Yu-Hung Wu, Shao-Xiang Yuan, Chan-Hung Yu, Zih-Ching Chen, Kuan-Hao Huang +1 morePublished Oct 19, 2026
arXiv PDF
Researcher verdict
Context only
Use as context only
Benchmark evidence
Missing
Not verified yet
Time to first repro
A few days
Plan setup time
Risk flags
2
Review before use

Abstract

Domain fit: AI-core · Core AI workload signals detected from paper context and implementation/artifact evidence.

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.

Results and benchmarks

Freshness tier: hot
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.

Implementation

No direct implementation yet

Maintained implementation evidence is not confirmed for this paper yet.

Use the implementation status and reproduction sections for the current action plan.

Implementation evidence summary
Confidence: low

Recommendation evidence is currently too limited for a maintained-repo choice. Use Implementation Status and Reproduction Path for a practical baseline plan.

Reproduction risks
  • Estimate is based on paper-only reproduction flow

Reproduction readiness

Time to first repro: days
Last checked: Nov 20, 2026

No repo

No verified implementation available

  • No maintained repository has been identified for this paper. Check adjacent implementations or HF artifacts below.

Hardware requirements

  • Expect multi-day setup/compute for meaningful reproduction based on current guidance.

Hugging Face artifacts

No trustworthy direct or curated related Hugging Face artifacts were found yet. Use targeted searches to quickly locate candidate models, datasets, and demos.

Tip: start with models, then check datasets and spaces if you need evaluation data or demos.

Research context

Tasks

None detected

Methods

Transformer

Domains

Natural Language Processing, Large Language Models

Evaluation and human feedback data

Open this paper in HFEPX to review benchmark signals, evaluation modes, and human-feedback protocol context.

Open in HFEPX
Explore similar papers

Jump to Paper2Code search queries derived from this paper's research context.