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

arXiv: https://arxiv.org/abs/2503.01141 · HTML: https://mlsanity.com/paper/2503.01141/

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 19 of its 24 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 19 of 19)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters](https://mlsanity.com/paper/2212.10001/) (2022)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [Distilling System 2 into System 1](https://mlsanity.com/paper/2407.06023/) (2024)
- [The Impact of Reasoning Step Length on Large Language Models](https://mlsanity.com/paper/2401.04925/) (2024)
- [C3oT: Generating Shorter Chain-of-Thought without Compromising Effectiveness](https://mlsanity.com/paper/2412.11664/) (2024)
- [Concise Thoughts: Impact of Output Length on LLM Reasoning and Cost](https://mlsanity.com/paper/2407.19825/) (2024)
- [The Benefits of a Concise Chain of Thought on Problem-Solving in Large Language Models](https://mlsanity.com/paper/2401.05618/) (2024)
- [Over-Reasoning and Redundant Calculation of Large Language Models](https://mlsanity.com/paper/2401.11467/) (2024)

## Built on by (most cited first, 30 of 97)

- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Dynamic Early Exit in Reasoning Models](https://mlsanity.com/paper/2504.15895/) (2025)
- [Thinking with Images for Multimodal Reasoning: Foundations, Methods, and Future Frontiers](https://mlsanity.com/paper/2506.23918/) (2025)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyond](https://mlsanity.com/paper/2503.21614/) (2025)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [S-GRPO: Early Exit via Reinforcement Learning in Reasoning Models](https://mlsanity.com/paper/2505.07686/) (2025)
- [AdaCoT: Pareto-Optimal Adaptive Chain-of-Thought Triggering via Reinforcement Learning](https://mlsanity.com/paper/2505.11896/) (2025)
- [Concise Reasoning via Reinforcement Learning](https://mlsanity.com/paper/2504.05185/) (2025)
- [ShorterBetter: Guiding Reasoning Models to Find Optimal Inference Length for Efficient Reasoning](https://mlsanity.com/paper/2504.21370/) (2025)
- [Effectively Controlling Reasoning Models through Thinking Intervention](https://mlsanity.com/paper/2503.24370/) (2025)
- [Speculative Thinking: Enhancing Small-Model Reasoning with Large Model Guidance at Inference Time](https://mlsanity.com/paper/2504.12329/) (2025)
- [SelfBudgeter: Adaptive Token Allocation for Efficient LLM Reasoning](https://mlsanity.com/paper/2505.11274/) (2025)
- [ARM: Adaptive Reasoning Model](https://mlsanity.com/paper/2505.20258/) (2025)
- [Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropy](https://mlsanity.com/paper/2508.03346/) (2025)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [Harnessing the Reasoning Economy: A Survey of Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.24377/) (2025)
- [Prolonged Reasoning Is Not All You Need: Certainty-Based Adaptive Routing for Efficient LLM/MLLM Reasoning](https://mlsanity.com/paper/2505.15154/) (2025)
- [ConCISE: Confidence-guided Compression in Step-by-step Efficient Reasoning](https://mlsanity.com/paper/2505.04881/) (2025)
- [Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models](https://mlsanity.com/paper/2505.16122/) (2025)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [Optimizing Anytime Reasoning via Budget Relative Policy Optimization](https://mlsanity.com/paper/2505.13438/) (2025)
- [Let LRMs Break Free from Overthinking via Self-Braking Tuning](https://mlsanity.com/paper/2505.14604/) (2025)
- [System-1.5 Reasoning: Traversal in Language and Latent Spaces with Dynamic Shortcuts](https://mlsanity.com/paper/2505.18962/) (2025)
- [VeriThinker: Learning to Verify Makes Reasoning Model Efficient](https://mlsanity.com/paper/2505.17941/) (2025)
- [Not All Tokens Are What You Need In Thinking](https://mlsanity.com/paper/2505.17827/) (2025)
- [Towards AI Search Paradigm](https://mlsanity.com/paper/2506.17188/) (2025)
- [Does Your Reasoning Model Implicitly Know When to Stop Thinking?](https://mlsanity.com/paper/2602.08354/) (2026)
- [Towards Concise and Adaptive Thinking in Large Reasoning Models: A Survey](https://mlsanity.com/paper/2507.09662/) (2025)
- [The Evolution of Thought: Tracking LLM Overthinking via Reasoning Dynamics Analysis](https://mlsanity.com/paper/2508.17627/) (2025)

## Abstract (arXiv)

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.