ZICQ
中 Log in / Sign up
Newsroom Research & Papers #LLM Complexity #Inference Tokens #Accuracy-Budget Curves #Supervised Fine-Tuning #Inference Cost

LLM Complexity: Measuring Inference Difficulty via Accuracy–Token Curves

Avatar of Mr.Xu

By Mr.Xu Compiled & Reviewed by Editorial

Published:

中文阅读 (Chinese) English Version
Co-reading Select any sentence in the article to highlight, annotate, or copy a quote card. Join discussion ↓

Summary:The paper challenges a common shortcut: more generated tokens do not monotonically mean that a task is harder in the classical asymptotic sense. LLM Complexity instead derives a scalar difficulty measure from the frontier between accuracy and output-token budget. Across diverse models, the resulting task rankings are reported to be highly consistent. The authors also use those rankings to build an easy-to-hard SFT curriculum that improves accuracy while consuming fewer tokens, and report more s


The central contribution of LLM Complexity is not relabeling output length as asymptotic time complexity; it explicitly rejects that equivalence and proposes an empirical, measurable ranking of task difficulty.

Core Finding: Token Count Is Not Classical Time Complexity

Classical computational complexity describes asymptotic growth in running steps or resource use as input size increases, focusing on the relationship between a problem and an algorithm. An LLM's generated-token count is policy-dependent: prompts, model versions, temperature, output limits, stopping rules, tool use, and response style can all change it.

The same task may require dozens of tokens from one model and thousands from another. Token consumption therefore measures inference effort only under a fixed model and decoding configuration; it cannot define the intrinsic complexity of the problem on its own. The paper reports that token usage does not align monotonically with classical time complexity and instead derives difficulty from observed model behavior.

From Accuracy–Token Curves to a Scalar Difficulty Measure

Let A_m,t(b) denote the accuracy on task t under model m with an output-token budget of b. Evaluating multiple budgets produces an accuracy–token frontier. According to the supplied abstract, LLM Complexity uses the area characterized by this curve to compress the frontier into a single difficulty score.

The intuition is straightforward. Easy tasks tend to reach high accuracy at smaller budgets, so their performance frontier rises earlier. Difficult tasks need larger inference budgets before accuracy improves. Unlike evaluating only the endpoint at the maximum budget, the area uses multiple budget points and is less dependent on a single successful or failed run.

The supplied abstract does not disclose the exact integration direction, normalization, token-accounting convention, or treatment of the zero-budget boundary. Those details are required for reproduction. The paper also reports highly consistent task rankings across diverse models, suggesting that the models share a stable notion of difficulty. That claim should nevertheless be tested with the complete model list, Spearman or Kendall correlations, confidence intervals, and leave-one-model-out validation rather than inferred from a qualitative statement alone.

Tokens Are Only a Partial Proxy for Inference Compute

An autoregressive Transformer performs projection computation and reads a growing KV Cache at every decoding step. Ignoring batching, cache effects, and constant factors, a rough dense-model inference cost estimate is:

C ≈ O(Ld² + L²d + T(d² + Ld))

where L is input length, T is output length, and d is the hidden dimension. This simplified expression shows that output tokens cover only part of inference cost. Prefill work, attention length, model size, active parameters in MoE architectures, GQA or MQA, quantization, batching, and KV-cache memory all affect real resource use. Speculative decoding can also accept multiple tokens per target-model forward pass, further decoupling output length from target-model steps.

LLM Complexity should therefore be treated as an empirical difficulty measure for a model ecosystem, not a hardware-independent complexity class. Production systems still need to evaluate it alongside TTFT, time per output token, P99 latency, throughput, KV-cache occupancy, and cost per million tokens.

Reported Empirical Signals and Evidence Boundaries

| Paper claim | Engineering implication | What must be verified | | --- | --- | --- | | Diverse models produce highly consistent task rankings | A common difficulty scale could support data selection, curriculum learning, and model routing | Full model list, correlation coefficients, confidence intervals, prompt templates, and leave-one-model-out generalization | | An easy-to-hard SFT curriculum improves accuracy while reducing token consumption | Training-example order may become an efficiency lever | Absolute accuracy, token reduction, random-order baselines, and matched data and compute budgets | | Cross-model correlations on real-world tasks are more stable than human difficulty labels | Model behavior can complement subjective annotations | Task set, annotator agreement, correlation definition, and external-dataset replication | | Token length does not align monotonically with classical time complexity | Output length should not continue to serve as a direct substitute for problem complexity | Counterexample definitions, statistical tests, and robustness across decoding configurations |

The available material provides no absolute scores, sample sizes, variance estimates, training costs, or code status. For the SFT claim in particular, a random-order or mixed-order baseline is essential. Without it, gains cannot be cleanly separated from curriculum effects, sample selection, or additional training compute.

Engineering Costs and Evaluation Risks

Constructing a complete accuracy–token curve is not cheap. With N tasks, R repeated generations per budget, and K budget levels, the evaluation requires at least N×R×K generations. The approximate generated-token volume is N×R×ΣB_j, before prefilling, failed retries, and judge-model calls.

Reproduction should control four major sources of variance. First, freeze model versions, system prompts, sampling settings, stopping rules, and token-accounting rules; otherwise the curve may primarily reflect configuration changes. Second, repeat sampling and use Bootstrap intervals so decoding noise is not mistaken for task difficulty. Third, keep the budget grid and maximum budget identical across tasks, or the areas will not represent comparable operating ranges. Fourth, inspect saturation explicitly: an easy task may immediately approach the accuracy ceiling, while a very hard task may remain near zero, and both cases can distort rankings.

Stable cross-model rankings do not automatically prove that an objective complexity has been discovered. Models may share training corpora, prompt conventions, and benchmark biases, causing them to form similar preferences over a task set. Stronger validation would cover different model families and capability tiers, external tasks excluded from initial calibration, and controlled comparisons with conventional input-size variables.

A Practical Deployment Path

  1. Build a reproducible baseline: Freeze models, prompts, sampling settings, tool permissions, and rules for counting visible and hidden reasoning tokens. Record per-sample accuracy, stop reasons, and actual consumption.
  2. Sample operational budgets: Cover typical and tail production ranges while retaining random ordering or existing heuristic ordering as a control.
  3. Estimate rather than hard-code difficulty: Use repeated runs and Bootstrap resampling to obtain distributions and confidence intervals. Recalibrate after model upgrades so old rankings are not frozen into a new system.
  4. Validate the SFT curriculum: Compare random, mixed, and easy-to-hard ordering under the same base model, data volume, training-token budget, and hyperparameters. Add replay to monitor catastrophic forgetting.
  5. Integrate routing and budget control: Allocate smaller budgets or cheaper models to easy tasks, then escalate the model or budget for difficult ones. Keep fallback paths because misclassification can cause direct output truncation.
  6. Monitor business metrics jointly: Track success rate, P95 and P99 latency, GPU utilization, peak KV-cache memory, and cost per successful task so a single efficiency metric does not increase total cost.

Conclusion

The paper's most defensible contribution is to recast problem difficulty as a measurable question about model accuracy under different inference budgets, rather than treating generated length or subjective annotations as the only difficulty signals. If the full results hold, this could improve training-data ordering, inference-budget allocation, and model routing.

The evidence is still limited to a preprint abstract. The exact metric definition, experimental scale, statistical significance, absolute gains, and implementation are unavailable, so LLM Complexity merits independent replication but should not yet be presented as a validated universal theory of computational complexity.


Source: ArXiv NLP/LLM (cs.CL) (2026-11-20)

— END —

Tags: #LLM Complexity #Inference Tokens #Accuracy-Budget Curves #Supervised Fine-Tuning #Inference Cost

Editorial & Fact-Checking Note: This article is compiled from primary research, official release documentation, and source papers by the ZICQ Newsroom pipeline with automated entity verification and human editorial review. If you notice any technical inaccuracy, please submit a correction via our corrections policy or email our editorial desk directly.

What's your take on this story?
🚀 Explore & Submit Works

Community Comments

Loading live comments and annotations…