---
title: "Time-for-Accuracy: Formalizing Chain-of-Thought as an Expansion of Logical Depth — Wang 2026"
description: "Chain-of-thought prompting often helps LLMs on multi-step problems, but it is unclear what extra computation a longer trace actually… 28 references."
authors: ["Yue Wang", "Zhi Zhang", "Wang Xi", "Chengjie Sun", "Lili Shan", "Bingquan Liu"]
year: 2026
venue: "Findings of the Association for Computational Linguistics: ACL 2026"
source: "https://aclanthology.org/2026.findings-acl.1938/"
doi: "10.18653/v1/2026.findings-acl.1938"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/wang-2026-time-accuracy-formalizing-chain-thought/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/wang-2026-time-accuracy-formalizing-chain-thought/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/10/) / Time-for-Accuracy: Formalizing Chain-of-Thought as an Expansion of Logical Depth

# Time-for-Accuracy: Formalizing Chain-of-Thought as an Expansion of Logical Depth

**Authors:** [Yue Wang](https://md.research.elamur.ai/free/en/authors/yue-wang/), Zhi Zhang, Wang Xi, Chengjie Sun, Lili Shan and Bingquan Liu · **Year:** 2026 · **Venue:** Findings of the Association for Computational Linguistics: ACL 2026 · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2026.findings-acl.1938/) · [PDF](https://aclanthology.org/2026.findings-acl.1938.pdf) · [DOI 10.18653/v1/2026.findings-acl.1938](https://doi.org/10.18653/v1/2026.findings-acl.1938) · [OpenAlex](https://openalex.org/W7166859603)

**Citations:** 0 citations (OpenAlex, 2026-10-14)

## Summary
Chain-of-thought prompting often helps LLMs on multi-step problems, but it is unclear what extra computation a longer trace actually provides. The authors use algorithmic information theory to frame the question. An answer can have a short description (low Kolmogorov complexity) and still require long sequential work to derive. Bennett's logical depth measures that sequential work. They treat a budget of T reasoning steps as a cap on the sequential computation a model can carry out. A stylized proposition then argues that a budget below a task's required depth leaves an unavoidable error floor, and that this floor disappears once the budget is large enough.

To measure how much of a trace a model truly relies on, they introduce Effective Logical Depth (ELD). ELD adds up, across steps, how often deleting a single step turns a correct answer into a wrong one under a chosen inference interface. Experiments on depth-controlled prefix-sum tasks and perturbed GSM8K rationales show two patterns: accuracy stays flat and then jumps as the budget grows, and only a few early steps are critical. ELD gives a verifier-free way to separate real computation from filler in reasoning traces.

## Key points
- ELD is defined as c·Σρ(t). Here ρ(t) is the expected rate at which removing step t breaks a previously correct answer. It is a behavioral measure that depends on the interface, not a model of transformer internals.
- The theory assumes a near-shortest-program bias. Under that assumption, the best achievable error is bounded below by the share of instances whose required depth exceeds the effective budget cT.
- Two GSM8K interfaces give different results:
  - Under EXTRACT, where the model reads the answer from what remains of the rationale, accuracy stays near-perfect after prefix deletions.
  - Under REPAIR, where the model must re-solve from truncated context, accuracy drops sharply.
  - Under REPAIR, SOCRATIC human rationales hold up better than MAIN ones.
- The appendix extends the analysis to more models and datasets and adds controls that continue generation under a fixed budget. It also tests perturbations that leave the format intact and reports significance tests. The controls indicate the performance drop is not explained by formatting shift alone.
- The evidence is limited to synthetic arithmetic and GSM8K, and the mapping from step budget to compute is qualitative. The work is from Harbin Institute of Technology and USTC, published in Findings of ACL 2026.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [🧮 Reasoning](https://md.research.elamur.ai/free/en/topics/reasoning/)

## Institutions

- [University of Science and Technology of China](https://md.research.elamur.ai/free/en/universities/university-of-science-and-technology-of-china/) — University, Hefei, China · 18 works · 109,489 citations
- [Harbin Institute of Technology](https://md.research.elamur.ai/free/en/universities/harbin-institute-of-technology/) — University, Harbin, China · 58 works · 25,250 citations

## Cite

Cite as: Yue Wang, Zhi Zhang, Wang Xi, Chengjie Sun, Lili Shan and Bingquan Liu. 2026. Time-for-Accuracy: Formalizing Chain-of-Thought as an Expansion of Logical Depth. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{wang2026time,
  title = {{Time-for-Accuracy: Formalizing Chain-of-Thought as an Expansion of Logical Depth}},
  author = {Yue Wang, Zhi Zhang, Wang Xi, Chengjie Sun, Lili Shan and Bingquan Liu},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1938},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1938}
}
```

- [← previous Tigrinya Number Verbalization: Rules, Algorithm, and Implementation](https://md.research.elamur.ai/free/en/papers/gaim-2026-tigrinya-number-verbalization-rules-algorithm/)
- [next → To Overfit or Not to Overfit? An Evaluation of HTR Workflow on 17Th-18Th Century French Corpus](https://md.research.elamur.ai/free/en/papers/tiger-2026-overfit-or-not-overfit-evaluation/)
- [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/10/)

## References

28 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Sriram Balasubramanian, Samyadeep Basu, and Soheil Feizi. 2025. A closer look at bias and chain-of-thought faithfulness of large (vision) language models. arXiv preprint arXiv:2505.23945. [find](https://scholar.google.com/scholar?q=Sriram+Balasubramanian%2C+Samyadeep+Basu%2C+and+Soheil+Feizi%2E+2025%2E+A+closer+look+at+bias+and+chain%2Dof%2Dthought+faithfulness+of+large+%28vision%29+language+models%2E+arXiv+preprint+arXiv%3A2505%2E23945%2E)
2. Kenza Benkirane, Laura Gongas, Shahar Pelles, Naomi Fuchs, Joshua Darmon, Pontus Stenetorp, David Ifeoluwa Adelani, and Eduardo Sánchez. 2024. Machine translation hallucination detection for low and high resource languages using large language models. arXiv preprint arXiv:2407.16470. [find](https://scholar.google.com/scholar?q=Kenza+Benkirane%2C+Laura+Gongas%2C+Shahar+Pelles%2C+Naomi+Fuchs%2C+Joshua+Darmon%2C+Pontus+Stenetorp%2C+David+Ifeoluwa+Adelani%2C+and+Eduardo+S%C3%A1nchez%2E+2024%2E+Machine+translation+hallucination+detection+for+low+and+h)
3. Charles H. Bennett. 1988. Logical depth and physical complexity. [find](https://scholar.google.com/scholar?q=Charles+H%2E+Bennett%2E+1988%2E+Logical+depth+and+physical+complexity%2E)
4. Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang, and Yunhe Wang. 2024. Forest-of-thought: Scaling test-time compute for enhancing llm reasoning. arXiv preprint arXiv:2412.09078. [find](https://scholar.google.com/scholar?q=Zhenni+Bi%2C+Kai+Han%2C+Chuanjian+Liu%2C+Yehui+Tang%2C+and+Yunhe+Wang%2E+2024%2E+Forest%2Dof%2Dthought%3A+Scaling+test%2Dtime+compute+for+enhancing+llm+reasoning%2E+arXiv+preprint+arXiv%3A2412%2E09078%2E)
5. Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. 2024. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787. [our card](https://md.research.elamur.ai/free/en/papers/brown-2024-large-language-monkeys-scaling-inference/)
6. Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. 2024. Alphamath almost zero: process supervision without process. Advances in Neural Information Processing Systems, 37:27689–27724. [our card](https://md.research.elamur.ai/free/en/papers/chen-2024-alphamath-almost-zero-process-supervision/)
7. Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. 2025. Towards reasoning era: A survey of long chain-of-thought for reasoning large language models. arXiv preprint arXiv:2503.09567. [our card](https://md.research.elamur.ai/free/en/papers/chen-2025-towards-reasoning-era-survey-long/)
8. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. [our card](https://md.research.elamur.ai/free/en/papers/cobbe-2021-training-verifiers-solve-math-word/)
9. Zeyu Gan, Yun Liao, and Yong Liu. 2025. Rethinking external slow-thinking: From snowball errors to probability of correct reasoning. arXiv preprint arXiv:2501.15602. — [arXiv:2501.15602](https://arxiv.org/abs/2501.15602) [find](https://scholar.google.com/scholar?q=Zeyu+Gan%2C+Yun+Liao%2C+and+Yong+Liu%2E+2025%2E+Rethinking+external+slow%2Dthinking%3A+From+snowball+errors+to+probability+of+correct+reasoning%2E+arXiv+preprint+arXiv%3A2501%2E15602%2E+%E2%80%94+%5BarXiv%3A2501%2E15602%5D%28https%3A%2F%2Farxiv)
10. Muhammad Khalifa, Rishabh Agarwal, Lajanugen Logeswaran, Jaekyeom Kim, Hao Peng, Moontae Lee, Honglak Lee, and Lu Wang. 2025. Process reward models that think. [find](https://scholar.google.com/scholar?q=Muhammad+Khalifa%2C+Rishabh+Agarwal%2C+Lajanugen+Logeswaran%2C+Jaekyeom+Kim%2C+Hao+Peng%2C+Moontae+Lee%2C+Honglak+Lee%2C+and+Lu+Wang%2E+2025%2E+Process+reward+models+that+think%2E)
11. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199– 22213. [our card](https://md.research.elamur.ai/free/en/papers/kojima-2022-large-language-models-zero-shot/)
12. Ming Li and Paul Vitányi. 2008. An introduction to Kolmogorov complexity and its applications, volume 3. Springer. [find](https://scholar.google.com/scholar?q=Ming+Li+and+Paul+Vit%C3%A1nyi%2E+2008%2E+An+introduction+to+Kolmogorov+complexity+and+its+applications%2C+volume+3%2E+Springer%2E)
13. Jianqiao Lu, Zhiyang Dou, Hongru Wang, Zeyu Cao, Jianbo Dai, Yunlong Feng, and Zhijiang Guo. 2024. Autopsv: Automated process-supervised verifier. Advances in Neural Information Processing Systems, 37:79935–79962. [find](https://scholar.google.com/scholar?q=Jianqiao+Lu%2C+Zhiyang+Dou%2C+Hongru+Wang%2C+Zeyu+Cao%2C+Jianbo+Dai%2C+Yunlong+Feng%2C+and+Zhijiang+Guo%2E+2024%2E+Autopsv%3A+Automated+process%2Dsupervised+verifier%2E+Advances+in+Neural+Information+Processing+Systems%2C+37)
14. William Merrill and Ashish Sabharwal. 2025. A little depth goes a long way: The expressive power of log-depth transformers. arXiv preprint arXiv:2503.03961. — [arXiv:2503.03961](https://arxiv.org/abs/2503.03961) [find](https://scholar.google.com/scholar?q=William+Merrill+and+Ashish+Sabharwal%2E+2025%2E+A+little+depth+goes+a+long+way%3A+The+expressive+power+of+log%2Ddepth+transformers%2E+arXiv+preprint+arXiv%3A2503%2E03961%2E+%E2%80%94+%5BarXiv%3A2503%2E03961%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F)
15. Akshara Prabhakar, Thomas L Griffiths, and R Thomas McCoy. 2024. Deciphering the factors influencing the efficacy of chain-of-thought: Probability, memorization, and noisy reasoning. arXiv preprint arXiv:2407.01687. [find](https://scholar.google.com/scholar?q=Akshara+Prabhakar%2C+Thomas+L+Griffiths%2C+and+R+Thomas+McCoy%2E+2024%2E+Deciphering+the+factors+influencing+the+efficacy+of+chain%2Dof%2Dthought%3A+Probability%2C+memorization%2C+and+noisy+reasoning%2E+arXiv+preprint+ar)
16. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314. [our card](https://md.research.elamur.ai/free/en/papers/snell-2024-scaling-llm-test-time-compute/)
17. Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. 2024. Chain of thoughtlessness? an analysis of cot in planning. Advances in Neural Information Processing Systems, 37:29106–29141. [find](https://scholar.google.com/scholar?q=Kaya+Stechly%2C+Karthik+Valmeekam%2C+and+Subbarao+Kambhampati%2E+2024%2E+Chain+of+thoughtlessness%3F+an+analysis+of+cot+in+planning%2E+Advances+in+Neural+Information+Processing+Systems%2C+37%3A29106%E2%80%9329141%2E)
18. Weiyun Wang, Zhangwei Gao, Lianjie Chen, and Zhe Chen. 2025. Visualprm: An effective process reward model for multimodal reasoning. arXiv preprint arXiv:2503.10291. — [arXiv:2503.10291](https://arxiv.org/abs/2503.10291) [find](https://scholar.google.com/scholar?q=Weiyun+Wang%2C+Zhangwei+Gao%2C+Lianjie+Chen%2C+and+Zhe+Chen%2E+2025%2E+Visualprm%3A+An+effective+process+reward+model+for+multimodal+reasoning%2E+arXiv+preprint+arXiv%3A2503%2E10291%2E+%E2%80%94+%5BarXiv%3A2503%2E10291%5D%28https%3A%2F%2Farxiv%2E)
19. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171. [our card](https://md.research.elamur.ai/free/en/papers/wang-2022-self-consistency-improves-chain-thought/)
20. Yiming Wang, Pei Zhang, Baosong Yang, Derek F Wong, and Rui Wang. 2024a. Latent space chain-of-embedding enables output-free llm self-evaluation. arXiv preprint arXiv:2410.13640. — [arXiv:2410.13640](https://arxiv.org/abs/2410.13640) [find](https://scholar.google.com/scholar?q=Yiming+Wang%2C+Pei+Zhang%2C+Baosong+Yang%2C+Derek+F+Wong%2C+and+Rui+Wang%2E+2024a%2E+Latent+space+chain%2Dof%2Dembedding+enables+output%2Dfree+llm+self%2Devaluation%2E+arXiv+preprint+arXiv%3A2410%2E13640%2E+%E2%80%94+%5BarXiv%3A2410%2E13640%5D%28)
21. Zihan Wang, Yunxuan Li, Yuexin Wu, Liangchen Luo, Le Hou, Hongkun Yu, and Jingbo Shang. 2024b. Multi-step problem solving through a verifier: An empirical analysis on model-induced process supervision. arXiv preprint arXiv:2402.02658. [find](https://scholar.google.com/scholar?q=Zihan+Wang%2C+Yunxuan+Li%2C+Yuexin+Wu%2C+Liangchen+Luo%2C+Le+Hou%2C+Hongkun+Yu%2C+and+Jingbo+Shang%2E+2024b%2E+Multi%2Dstep+problem+solving+through+a+verifier%3A+An+empirical+analysis+on+model%2Dinduced+process+supervision)
22. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837. [our card](https://md.research.elamur.ai/free/en/papers/wei-2022-chain-thought-prompting-elicits-reasoning/)
23. Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. 2024. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.00724. [our card](https://md.research.elamur.ai/free/en/papers/wu-2024-inference-scaling-laws-empirical-analysis/)
24. Zhiheng Xi, Chenyang Liao, Guanyu Li, Yajie Yang, Wenxiang Chen, Zhihao Zhang, Binghai Wang, Senjie Jin, Yuhao Zhou, Jian Guan, and 1 others. 2025. Agentprm: Process reward models for llm agents via step-wise promise and progress. arXiv preprint arXiv:2511.08325. — [arXiv:2511.08325](https://arxiv.org/abs/2511.08325) [find](https://scholar.google.com/scholar?q=Zhiheng+Xi%2C+Chenyang+Liao%2C+Guanyu+Li%2C+Yajie+Yang%2C+Wenxiang+Chen%2C+Zhihao+Zhang%2C+Binghai+Wang%2C+Senjie+Jin%2C+Yuhao+Zhou%2C+Jian+Guan%2C+and+1+others%2E+2025%2E+Agentprm%3A+Process+reward+models+for+llm+agents+via+s)
25. Ori Yoran, Kunhao Zheng, Fabian Gloeckle, Jonas Gehring, Gabriel Synnaeve, and Taco Cohen. 2025. The kolmogorov test: Compression by code generation. arXiv preprint arXiv:2503.13992. — [arXiv:2503.13992](https://arxiv.org/abs/2503.13992) [find](https://scholar.google.com/scholar?q=Ori+Yoran%2C+Kunhao+Zheng%2C+Fabian+Gloeckle%2C+Jonas+Gehring%2C+Gabriel+Synnaeve%2C+and+Taco+Cohen%2E+2025%2E+The+kolmogorov+test%3A+Compression+by+code+generation%2E+arXiv+preprint+arXiv%3A2503%2E13992%2E+%E2%80%94+%5BarXiv%3A2503%2E139)
26. Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Wenyue Hua, Haolun Wu, Zhihan Guo, Yufei Wang, Niklas Muennighoff, and 1 others. 2025a. A survey on test-time scaling in large language models: What, how, where, and how well? arXiv preprint arXiv:2503.24235. [find](https://scholar.google.com/scholar?q=Qiyuan+Zhang%2C+Fuyuan+Lyu%2C+Zexu+Sun%2C+Lei+Wang%2C+Weixu+Zhang%2C+Wenyue+Hua%2C+Haolun+Wu%2C+Zhihan+Guo%2C+Yufei+Wang%2C+Niklas+Muennighoff%2C+and+1+others%2E+2025a%2E+A+survey+on+test%2Dtime+scaling+in+large+language+model)
27. Wenlin Zhang, Xiangyang Li, Kuicai Dong, Yichao Wang, Pengyue Jia, Xiaopeng Li, Yingyi Zhang, Derong Xu, Zhaocheng Du, Huifeng Guo, and 1 others. 2025b. Process vs. outcome reward: Which is better for agentic rag reinforcement learning. arXiv preprint arXiv:2505.14069. — [arXiv:2505.14069](https://arxiv.org/abs/2505.14069) [find](https://scholar.google.com/scholar?q=Wenlin+Zhang%2C+Xiangyang+Li%2C+Kuicai+Dong%2C+Yichao+Wang%2C+Pengyue+Jia%2C+Xiaopeng+Li%2C+Yingyi+Zhang%2C+Derong+Xu%2C+Zhaocheng+Du%2C+Huifeng+Guo%2C+and+1+others%2E+2025b%2E+Process+vs%2E+outcome+reward%3A+Which+is+better+for)
28. Chujie Zheng, Zhenru Zhang, Beichen Zhang, Runji Lin, Keming Lu, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. 2025. Processbench: Identifying process errors in mathematical reasoning. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long… [our card](https://md.research.elamur.ai/free/en/papers/zheng-2025-processbench-identifying-process-errors-mathematical/)