跳到正文
arXiv cs.CL· Yu-Hung Wu, Shao-Xiang Yuan, Chan-Hung Yu, Zih-Ching Chen, Kuan-Hao Huang, Shao-Hua Sun·· 10 小时前AI 评分34

LLM Complexity:从计算复杂度视角理解大语言模型推理

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

AI 导读

研究者提出 LLM Complexity 新指标,通过准确率-token 曲线所围面积量化任务难度,并证伪了 token 用量与经典时间复杂度单调对应的假设。不同 LLM 在该指标下给出高度一致的任务难度排序,据此构建的由易到难课程用于监督微调,可在提升准确率的同时降低 token 消耗。该指标在真实任务上的跨模型相关性也比人工标注难度标签更稳定。

正文 · 原文

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)

来源:arXiv cs.CL · arxiv.org