PaperlayerView exact revision on arXiv

Source-linked AI summary

How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach

Ayeong Lee, Ethan Che, Tianyi Peng

arXiv:2503.01141v2cs.CLcs.AI

TL;DR

LLM chain-of-thought can be effective but costly, and the best way to compress reasoning without sacrificing accuracy remains unclear. The paper systematically evaluates compression prompts, identifies question-level token complexity behind a universal length–accuracy tradeoff, and finds existing prompt-based methods far from the optimal frontier.

  • Problem

    The paper addresses the lack of comprehensive evidence on how different chain-of-thought compression strategies affect response length and accuracy.

  • Method

    The authors evaluate diverse compression prompts and use token complexity with rate-distortion-inspired optimization to characterize accuracy–length limits.

  • Results

    Across diverse reasoning chains, accuracy primarily tracks response length, while question-level token complexity predicts CoT strategy performance with 94% accuracy and existing prompts remain far from the optimal frontier.

  • Takeaways & Limitations

    Token complexity provides a benchmark for reasoning efficiency and for assessing adaptive compression that uses shorter chains on easier questions.

  • Takeaways & Limitations

    The universal tradeoff is expected to hold only for reasonably informative chains and is less consistent for less capable models on harder datasets.

Abstract

from arXiv · show

Chain-of-thought prompting has emerged as a powerful technique for enabling large language models (LLMs) to solve complex reasoning tasks. However, these reasoning chains can be verbose, raising concerns about efficiency. In response, recent works have sought to decrease response lengths through simple prompting strategies (e.g. 'be concise'). In this work, we conduct the first systematic study of the relationship between reasoning length and model performance across a diverse range of compression instructions (e.g. 'use 10 words or less' or 'remove all punctuation'). In doing so, we discover a universal tradeoff between reasoning length and accuracy that persists across even very distinct reasoning chains. We demonstrate that this tradeoff emerges from a sharp threshold behavior at the question level: each task has an intrinsic 'token complexity' - a minimal number of tokens required for successful problem-solving. We show how token complexity enables us to compute information-theoretic limits on the accuracy-compression tradeoff, and find that prompt-based compression strategies operate far from these theoretical limits. This suggests there may be significant room for improvement and our framework provides a benchmark to help researchers evaluate progress in reasoning efficiency. Our work also highlights the importance of adaptive compression -- giving shorter responses for easier questions -- and we show that token complexity is a useful tool for measuring this capability.

1 Introduction

This study examines how prompt-based compression changes the length and accuracy of chain-of-thought reasoning. It finds a universal length–accuracy tradeoff, introduces question-level token complexity, and shows existing strategies remain far from optimal compression.

  • Motivation: LLM reasoning can improve complex problem-solving but often generates lengthy intermediate computations that increase inference costs.The paper motivates efficient reasoning strategies for real-world deployment.
  • Research gap: Prior compression prompts reduce response length but produce varying accuracy degradation, leaving the best compression strategy unclear.The study considers alternatives involving words, tokens, reasoning steps, punctuation, filler words, and formatting.
  • Study design: The paper evaluates 31 compression prompts across six LLMs and three standard reasoning datasets to systematically measure length–performance tradeoffs.The prompts include “be concise,” word and token limits, bullet points, and character constraints.
  • Main findings: Different chains of thought largely fall on a universal tradeoff curve, indicating that reasoning length affects accuracy more than chain composition.The pattern is reported across distinct prompt formats and benchmark settings.
  • Token complexity: Token complexity is the minimum number of tokens required for a question to be solved successfully, and it predicts CoT strategy performance with 94% accuracy.The threshold is defined at the question level and holds across diverse prompting strategies.
  • Theoretical limits: Rate-distortion-inspired bounds show prompt-based compression operates far from optimal, leaving substantial room to improve accuracy–compression tradeoffs.The framework also supports evaluating adaptive reasoning that uses shorter chains for easier questions.

2 Experiments

Across three math-reasoning datasets and six LLMs, 31 compression prompts produced varied response lengths and accuracies, revealing substantial shortening opportunities and a near-universal length–accuracy trade-off. The experiments also show model-dependent prompt effectiveness and that token complexity closely predicts performance.

  • 31 prompts were evaluated across six LLMs on MATH-500, GSM8K, and MMLU-Pro Math.
  • Up to 60% length reduction relative to DefaultCoT was possible without sacrificing much accuracy.
  • BeConcise consistently shortened responses without significantly hurting performance, while OnlyNumbers and NoProperGrammar achieved similar accuracy with about 50% fewer GPT-4o tokens.
  • No prompt was universally dominant: OnlyNumbers and NoProperGrammar worked well for GPT-4o and Claude 3.5 Sonnet but less well for LLaMA 3.3 70B.
  • Nearly all prompts followed a near-identical response-length–accuracy curve across formatting and limiting strategies, suggesting limited gains from changing chain-of-thought composition alone.
  • Token complexity predicted overall benchmark performance within 6% error, with smaller errors for larger models on easier benchmarks.

3 The Token Complexity Hypothesis

The token complexity hypothesis proposes that each question has a minimum response length needed for correct solving, producing threshold-like behavior across prompting strategies. Threshold-based token length predicts question- and benchmark-level reasoning performance with high accuracy and low error.

  • Token Complexity Hypothesis: Across prompts, correctness exhibits a sharp threshold pattern: responses above a question-specific length are generally correct, while shorter responses are generally wrong.For one MATH-500 question, nearly all prompts exceeding approximately 53 tokens succeeded, with two exceptions.
  • Token Complexity Hypothesis: Each question has a token complexity, a minimum number of tokens required for successful problem-solving across prompts.The hypothesis is intended for reasonable chains-of-thought and treats more difficult problems as requiring more tokens.
  • Testing the Hypothesis: The study tests threshold predictability using 31 chain-of-thought prompts for each question across LLMs and reasoning benchmarks.The classifier predicts success or failure from whether chain-of-thought token length exceeds a threshold.
  • Empirical Validation: Average threshold-classifier accuracy exceeds 90% for most models and benchmarks, supporting a threshold relationship between token length and performance.Accuracy is higher for more capable models and easier benchmarks such as GSM8K.
  • Empirical Validation: The token-complexity model predicts benchmark performance within 6% relative error, with smaller errors for larger models on easier benchmarks.The comparison evaluates actual prompt accuracy against accuracy predicted from estimated token complexities.

4 Theoretical Limits of the Length-Performance Tradeoff

The paper uses token complexity to derive theoretical limits for the accuracy–length tradeoff, treating compression as an optimization over the minimum tokens needed for each question. Existing prompting strategies remain substantially above the attainable compression frontier.

  • Theoretical bounds: Rate-distortion-inspired bounds define the optimal accuracy α∗(T) for a token budget T and the minimum length T∗(α) for target accuracy α.The original optimization over prompts is simplified to optimization over token lengths under the token-complexity hypothesis.
  • Token-complexity optimization: Token complexity is the minimum number of tokens required to solve a question successfully, and optimal allocation uses that minimum.Under the stated assumption, questions are sorted by token complexity under a limited budget; equal weighting yields a closed-form solution.
  • Practical constraints: Approaching the theoretical limits requires knowing token complexities, matching them precisely, and prioritizing easier questions under the budget.The practical upper bound may therefore be difficult for feasible prompting techniques to reach.
  • Theoretical bounds: The oracle upper bound provides a computable maximum accuracy for a token budget and remains above evaluated prompting strategies, especially on MATH-500 and MMLU-Pro Math.The bound is computed using estimated token complexities and is described as reasonable even where it may be difficult to attain.
  • Compression limits: Lossless compression requires only the mean token complexity to achieve the best possible accuracy, which can be much shorter than existing prompt outputs.Across models, BeConcise reduces token counts by 1.2–1.4x, whereas the optimal compression scheme achieves 3.2–11.2x reduction.
  • Efficiency measurement: Token complexity also distinguishes reasoning efficiency when accuracy is similar: on GSM8K, Sonnet averages 17.9 tokens versus Haiku’s 42.4 under comparable DefaultCoT accuracy.DefaultCoT accuracy is 97% for Claude 3.5 Sonnet and 95% for Claude 3.5 Haiku.

5 Towards the Theoretical Limit

The paper evaluates whether adaptive reasoning can approach the theoretical frontier by matching response length to question difficulty. Simple prompting already tracks token complexity similarly to an explicit adaptive method, while verifier routing achieves a better tradeoff.

  • Adaptive compression: Adaptive compression is motivated by using shorter chains for easier questions, which could help approach the theoretical accuracy–length limit.The framework is used to evaluate methods that calibrate chain-of-thought length to problem difficulty.
  • Adaptive prompting: TALE-EP estimates the minimum required tokens before prompting the LLM to reason step-by-step with that guessed length.The method is evaluated against the accuracy–length tradeoff for GPT-4o on MMLU-Pro Math.
  • Adaptive prompting: TALE-EP’s token-complexity correlation is similar to NoProperGrammar’s: Spearman ρ = 0.51 versus ρ = 0.54.NoProperGrammar does not explicitly prompt adaptive reasoning, suggesting comparable response-length adaptation in this comparison.
  • Verifier routing: Verifier Routing improves the accuracy–length tradeoff by using NoCoT first and invoking longer chain-of-thought only when the initial solution is incorrect.Its results are closer to the upper bound than the simpler prompting strategies shown in Figure 3.

6 Conclusion

The paper finds a universal accuracy–length tradeoff across prompting strategies and explains it through question-level token-complexity thresholds. Its theoretical framework shows that current prompt-based compression remains far from optimal and can benchmark future adaptive methods.

  • 6 Conclusion: Reasoning length, rather than the specific compression strategy, primarily determines accuracy along a universal Pareto curve.The study compares diverse prompts and finds similar tradeoffs despite different chains of thought.
  • 6 Conclusion: A question is successfully solved only when its chain of thought exceeds an intrinsic token-complexity threshold.This threshold behavior is observed at question level across prompting strategies.
  • 6 Conclusion: Rate-distortion-inspired analysis places existing prompt-based compression far from the optimal accuracy–length frontier.The gap indicates room to evaluate and improve chain-of-thought compression and adaptivity.

A Limitations

The study’s conclusions are bounded by its mathematical-task setting, computationally expensive token-complexity estimation, and assumptions about cross-model consistency.

  • A Limitations: The study is limited to mathematical reasoning, so its accuracy–length tradeoffs and token-complexity thresholds may not extend to other domains.Unexamined domains include commonsense reasoning, code generation, and open-ended text generation.
  • A Limitations: The theoretical upper bound is rarely achieved because estimating token complexities and generating precisely compressed responses are practically difficult.Computing token complexity requires multiple generations per question, limiting large-scale applicability.
  • A Limitations: The approach assumes token complexity is well-defined and consistent across models and tasks, which may fail for some LLMs or complex benchmarks.The experiments also cover only a fixed set of 31 prompts.

B Correlation with Token Complexity

Token length is only moderately aligned with question-level token complexity, while response lengths are shorter on easier problems than on harder ones. The reported tradeoff tables organize accuracy against average response length across benchmarks.

  • Correlation results: 0 - 0.6: Spearman correlation between token-lengths and token-complexity across prompts for GPT-4o on MMLU-Pro Math.The prompt with the highest correlation varies across models and benchmarks.
  • Adaptive response length: Easy MMLU-Pro Math problems have universally shorter average responses than problems that NoCoT fails to solve.This ordering also holds for WordLimit, TokenLimit, and CharLimit prompts.
  • Tradeoff tables: Tables 6–8 describe accuracy-length tradeoffs for MMLU-Pro Math, GSM8K, and MATH-500.The supplied passages identify the table topics but do not provide their numerical entries.

D Proof of Theorem 1

Under the stated assumption, the optimization is reformulated as a knapsack problem. With equal question weights, its optimal policy greedily selects questions by increasing token complexity within the token budget.

  • Formulation: Under Assumption 1, the accuracy expression is used to formulate the optimization problem.The supplied passage introduces the representation and the subsequent optimization without displaying the equations.
  • Optimization: The optimal strategy sets each response length t_i to either its token complexity τ_i or 0.This reduces the decision to attempting a question at its required length or not attempting it.
  • Knapsack reduction: The resulting problem is a knapsack problem with unit rewards because all questions are weighted equally.The indicators x_i record whether the LLM attempts each question.
  • Greedy solution: The optimal policy greedily sorts questions by increasing token complexity and solves as many as fit within the budget.The threshold t_T is the highest token-complexity value included after greedy ordering.

F Tradeoff curves for more models and benchmarks

Across additional models and benchmarks, prompt-induced reasoning lengths and accuracies broadly follow the same tradeoff curve. The supplied figures show tradeoff curves and actual-versus-predicted accuracy comparisons for GSM8K and MATH-500.

  • Cross-model and benchmark results: Performance across all prompts broadly lies on the same trade-off curve for GSM8K and MATH-500.This result is reported across different models and benchmarks.
  • GSM8K: Figure 5 presents tradeoff curves for GSM8K.The supplied figure title does not state the direction or magnitude of the plotted comparison.
  • MATH-500: Figure 6 presents tradeoff curves for MATH-500.The supplied figure title does not state the direction or magnitude of the plotted comparison.
  • Accuracy prediction: Figures 7 and 8 compare actual versus predicted accuracy for GSM8K and MATH-500, respectively.The supplied titles identify the comparison but do not provide numerical outcomes.

H Routing Performance on other benchmarks

The supplied passage identifies Figure 9 as reporting prompt-routing performance on MATH-500 and GSM8K.

  • Prompt routing: Figure 9 reports the performance of prompt routing on MATH-500 and GSM8K.No result, comparison, or numerical outcome is provided in the supplied passage.
Loading 2503.01141v2…