REVIEW 3 major objections 6 minor 30 references
From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval
T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper proposes State Machine Reasoning (SMR), which replaces token-level chain-of-thought with discrete Refine, Rerank, and Stop actions over a structured state of query and retrieved documents, and reports a 3.4% nDCG@10 gain with a…
desk verdict SMR brings a useful state-machine action loop to LLM-based IR and shows big token savings, but its retrieval-effectiveness gains over rerank-only CoT baselines are confounded by the extra retrieval that REFINE performs. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the reasoning state $s_t=(q_t, D_t)$, where $q_t$ is the current query and $D_t=\{d_1,\dots,d_k\}$ is a ranked list of retrieved documents, together with an action space $\mathcal{A}=\{\text{REFINE},\text{RERANK},\text{STOP}\}$. REFINE rewrites the query conditioned on the retrieved documents and then invokes the retriever again, appending any newly found documents to the list; RERANK reorders the list under structural constraints that discard hallucinated entries and restore omitted ones; STOP terminates and returns the current state. The policy that picks the next action is itself an LLM prompted with a rule-based decision procedure, so no training or reward engineering is needed. The machinery that prevents overthinking is the equivalence check between consecutive states: if the query is unchanged and the document list is identical, the system concludes that further reasoning would be redundant and can stop.
What would settle it
Run SMR with the REFINE action disabled so that only RERANK and STOP operate on the same initial top-$k$ list used by the CoT baselines, and compare nDCG@10 against Rank1 and Rank-R1 on the same list; if the advantage disappears or reverses, the claimed benefit is not from state-machine reasoning but from the additional retrieval triggered by REFINE. Conversely, giving the baselines the same retrieve-and-append capability would test the same point from the other side.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that modelling LLM reasoning for IR as transitions over structured states $(q_t, D_t)$—a query plus a ranked list of top-$k$ documents—with three discrete actions (REFINE for query rewriting, RERANK for reordering documents, STOP for termination) yields both better retrieval and far less computation than token-level chain-of-thought. SMR detects redundancy by treating a state as equivalent to its predecessor when the query is unchanged and the document list is identical, and it grounds each action in the retrieval context so that reasoning cannot drift from user intent. In experiments on BRIGHT and BEIR, the framework reports consistent nDCG@10 improvements over standard CoT rerankers (Rank1, Rank-R1) and a compressed CoT method (O1-Pruner), with an average token reduction of 74.4%, and the paper argues the improvement comes from the structured action policy rather than from task-specific training or reward engineering.
Load-bearing premise
The load-bearing premise is that the CoT baselines are evaluated on the same footing as SMR; if the comparison instead gives SMR extra retrieval passes that Rank1 and Rank-R1 never receive, the reported gains could come from the larger document pool rather than from state-machine reasoning.
Editorial extensions
If this is right
- Retrieval systems can trade verbose reasoning traces for a three-action control loop and obtain better rankings at a fraction of the inference cost.
- Because the policy is prompt-based and the state only contains a query and a ranked list, SMR can be dropped into existing pipelines that use any retriever and any instruction-following LLM, with no fine-tuning.
- Early stopping becomes a principled decision grounded in state equivalence rather than a free parameter, which makes deployed retrieval more predictable in cost.
- The framework directly addresses the two failure modes the paper names—redundant trajectories and intent drift—by construction: redundancy triggers a stop, and each action is anchored to retrieval context.
- If the reported token reductions hold in practice, SMR-style reasoning offers a path to deploying reasoning LLMs in latency- and cost-sensitive search settings where CoT's verbosity is prohibitive.
Reading between the lines
- Beyond the paper: a testable extension is to run SMR with REFINE disabled so that only RERANK and STOP operate on the same initial top-$k$ list used by the CoT baselines; if the advantage disappears or reverses, the gain may come from the additional retrieval passes rather than from the state-machine policy itself.
- Beyond the paper: the equivalence-based stop condition could generalize to other agentic tasks where state can be canonicalized, such as code generation with a file-state or planning with a world-state, not just retrieval.
- Beyond the paper: because the action policy is prompt-based, it could be specialized per domain by editing the decision-policy text (for example, encouraging more REFINEs for acronym-heavy queries) without retraining the LLM.
- Beyond the paper: the paper counts only output tokens for efficiency; a fuller accounting that includes input tokens (long prompts with document lists repeated each step) would clarify the real latency benefit in practice.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes State Machine Reasoning (SMR), a prompting framework for information retrieval in which an LLM repeatedly chooses among three discrete actions—REFINE, RERANK, and STOP—operating on a structured state (query, top-k document list). The authors evaluate SMR on the BRIGHT and BEIR benchmarks with BM25 and ReasonIR as underlying retrievers, comparing against CoT-based rerankers (Rank1, Rank-R1) and a compressed-CoT baseline (O1-Pruner). They report improved nDCG@10 and large reductions in inference tokens, with claims of generalization across LLMs and retrievers without task-specific tuning.
Significance. If the reported effects are causally attributable to the state-machine design, SMR would be a useful and practical contribution: it offers interpretable, controllable reasoning steps, early stopping, and substantial token savings compared with verbose CoT, while requiring no task-specific training and only a single prompt. The paper also follows good empirical hygiene in several respects: hyperparameters are fixed in advance, the code is released, ablations compare the learned policy against fixed policies, intent preservation during refinement is measured, and qualitative case studies illustrate the failure modes of CoT baselines. However, the central retrieval-effectiveness claim is currently confounded by an unequal retrieval budget, so the main quantitative contribution is not yet established.
major comments (3)
- [Section 3.2, Appendix A.5] The comparison between SMR and the CoT baselines is confounded by unequal access to new documents. In Section 3.2, after each REFINE action the paper states that "we invoke the retriever with the updated query qt+1 to obtain new candidate documents" and appends unseen documents to the list, whereas Rank1, Rank-R1, and O1-Pruner are described as reranking a fixed initial pool. Appendix A.5, Table 6 confirms the asymmetry: Rank1 and Rank-R1 have Recall@10 identical to BM25 on every BRIGHT subset, while SMR raises average Recall@10 from 17.1 to 20.8. The reported nDCG@10 gains (RQ1, +5.4% sparse and +2.1% dense) may therefore reflect a larger evidence pool rather than the state-machine action structure, early stopping, or transition-based reasoning. The paper needs a matched control that gives the baseline methods the same iterative query rewriting and document appending capability, or that runs SMR's REFINE loop without the learned policy (e.g., random action selection or a fixed refine-then-stop rule). Without such a control, the central claim that SMR improves retrieval effectiveness is not supported.
- [Abstract, Section 1, Section 4.2.1] The headline numbers are internally inconsistent. The abstract reports a 3.4% nDCG@10 improvement and 74.4% token reduction; Section 1 reports 'up to 3.4%' and 74.7%; RQ1 (Section 4.2.1) reports +5.4% on sparse and +2.1% on dense retrievers, which do not average to 3.4%. Token reduction computed from Table 10 for SMR (Qwen2.5-32B) versus Rank1 is 74.7%, not 74.4%. The authors should choose one consistent set of summary statistics and explain exactly which comparisons each number refers to.
- [Section 4.2.1, Table 2] The text states that experiments are run "under both sparse (BM25) and dense (DPR) retrieval settings," but Table 2 uses ReasonIR as the dense retriever, not DPR. This mismatch makes the dense-retriever result ambiguous; if ReasonIR is a trained dense retriever but not DPR, the text should name it precisely and cite the corresponding setting consistently.
minor comments (6)
- [Section 1] The sentence "can resulting in outputs that diverge from user intent" contains a grammatical error; it should read "can result in outputs that diverge from user intent."
- [Table 1] The row for Rank1 (32B) contains the run-together entry "22.99.75.9", which appears to be a typesetting error with missing separators between four numeric values.
- [Figure 4 caption] The caption lists "Bio, Earth, Econ, Pay, Rob" as representative datasets; the BRIGHT benchmark includes a dataset called "Pony", so "Pay" is likely a typo and should be corrected.
- [Section 3.1, Eq. (1)] Equation (1) has malformed spacing and subscripts: "D t ={d 1, d2, . . . , dk}" should be formatted as D_t = {d_1, d_2, ..., d_k} for consistency with the rest of the paper.
- [Appendix A.4] The implementation details use inconsistent notation for the same hyperparameter: the main text and Section 3.2 say "top_k" and "k=10", while Appendix A.4 writes "top-k retrieval" and "k=10"; unify the notation, and also check that "batch_size" is defined consistently.
- [Table 10] Several token counts in Table 10 are formatted without thousands separators or with ambiguous spacing (e.g., "9827801,063914 996"), making the table hard to read; ensure proper formatting in the camera-ready version.
Circularity Check
No significant circularity: SMR is an empirical framework comparison, not a derivation; the REFINE retrieval-budget asymmetry is a confound, not circular reasoning.
full rationale
SMR is presented as a proposed framework and empirically evaluated, not derived from prior theorems or from its own outputs. No parameters are fitted to the test sets; hyperparameters such as k=10, max_steps=16, and temperature=0 are fixed in Appendix A.4 and held constant across datasets and models. The central claims are supported by benchmark comparisons against external baselines (Rank1, Rank-R1, O1-Pruner) that are not constructed from SMR's own quantities. The only notable concern is that the REFINE action appends newly retrieved documents to the list while the CoT baselines rerank only the initial top-k list, visible in Appendix A.5 where the baselines' Recall@10 exactly matches BM25. That is an experimental confound or uncontrolled variable, not circularity: the reported nDCG@10 gains do not reduce by definition to the framework's inputs, and there is no fitted parameter renamed as a prediction. No load-bearing argument relies on self-citation, and no uniqueness theorem or ansatz is imported from the authors' prior work. Therefore no circular step is identified and the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- max_steps =
16
- top_k =
10
- temperature =
0.0
assumptions (3)
- domain assumption The LLM policy can reliably choose the action that improves retrieval quality.
- domain assumption The base retriever (BM25 or ReasonIR) provides a useful initial ranking that query refinement can improve.
- domain assumption The GPT-4o-mini intent-alignment scores correctly measure whether refinements preserve user intent.
Cite this review
Pith. "Pith review of From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval." pith.science (2026). https://pith.science/paper/T3SOVF4Z
@misc{pith2026250523059,
author = {Pith},
title = {Pith review of: From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval},
year = {2026},
howpublished = {\url{https://pith.science/paper/T3SOVF4Z}},
note = {Machine review of arXiv:2505.23059}
}
read the original abstract
Chain-of-Thought (CoT) prompting enables complex reasoning in large language models (LLMs), including applications in information retrieval (IR). However, it often leads to overthinking, where models produce excessively long and semantically redundant traces with little or no benefit. We identify two key challenges in IR: redundant trajectories that revisit similar states and misguided reasoning that diverges from user intent. To address these, we propose State Machine Reasoning (SMR), a transition-based reasoning framework composed of discrete actions (Refine, Rerank, Stop) that support early stopping and fine-grained control. Experiments on the BEIR and BRIGHT benchmarks show that SMR improves retrieval performance (nDCG@10) by 3.4% while reducing token usage by 74.4%. It generalizes across LLMs and retrievers without requiring task-specific tuning, offering a practical alternative to conventional CoT reasoning. The code and details are available at https://github.com/ldilab/SMR.
Figures
Reference graph
Works this paper leans on
-
[1]
Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, et al. 2024. Do not think that much for 2+ 3=? on the overthinking of o1-like llms. arXiv preprint arXiv:2412.21187
arXiv 2024
-
[2]
Chenrui Fan, Ming Li, Lichao Sun, and Tianyi Zhou. 2025. Missing premise exacerbates overthinking: Are reasoning models losing critical thinking skill? arXiv preprint arXiv:2504.06514
arXiv 2025
-
[3]
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948
arXiv 2025
-
[4]
Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. 2021. Unsupervised dense information retrieval with contrastive learning. arXiv preprint arXiv:2112.09118
arXiv 2021
-
[5]
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick SH Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In EMNLP (1), pages 6769--6781
2020
-
[6]
Xiaomin Li, Zhou Yu, Zhiwei Zhang, Xupeng Chen, Ziji Zhang, Yingying Zhuang, Narayanan Sadagopan, and Anurag Beniwal. 2025 a . When thinking fails: The pitfalls of reasoning for instruction-following in llms. arXiv preprint arXiv:2505.11423
arXiv 2025
-
[7]
Xiaoxi Li, Guanting Dong, Jiajie Jin, Yuyao Zhang, Yujia Zhou, Yutao Zhu, Peitian Zhang, and Zhicheng Dou. 2025 b . Search-o1: Agentic search-enhanced large reasoning models. arXiv preprint arXiv:2501.05366
arXiv 2025
-
[8]
Jia Liu, Jie Shuai, and Xiyao Li. 2023. State machine of thoughts: Leveraging past reasoning trajectories for enhancing problem solving. arXiv preprint arXiv:2312.17445
arXiv 2023
Show all 30 references
-
[9]
Ryan Liu, Jiayi Geng, Addison J Wu, Ilia Sucholutsky, Tania Lombrozo, and Thomas L Griffiths. 2024. Mind your step (by step): Chain-of-thought can reduce performance on tasks where thinking makes humans worse. arXiv preprint arXiv:2410.21333
2024 arXiv
-
[10]
Haotian Luo, Li Shen, Haiying He, Yibo Wang, Shiwei Liu, Wei Li, Naiqiang Tan, Xiaochun Cao, and Dacheng Tao. 2025. O1-pruner: Length-harmonizing fine-tuning for o1-like reasoning pruning. arXiv preprint arXiv:2501.12570
2025 arXiv
-
[11]
Xinbei Ma, Yeyun Gong, Pengcheng He, Hai Zhao, and Nan Duan. 2023. Query rewriting in retrieval-augmented large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5303--5315
2023
-
[12]
Xueguang Ma, Liang Wang, Nan Yang, Furu Wei, and Jimmy Lin. 2024. Fine-tuning llama for multi-stage text retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2421--2425
2024
-
[13]
Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage re-ranking with bert. arXiv preprint arXiv:1901.04085
2019 arXiv
-
[14]
Xiaoye Qu, Yafu Li, Zhaochen Su, Weigao Sun, Jianhao Yan, Dongrui Liu, Ganqu Cui, Daizong Liu, Shuxian Liang, Junxian He, et al. 2025. A survey of efficient reasoning for large reasoning models: Language, multimodality, and beyond. arXiv preprint arXiv:2503.21614
2025
-
[15]
Stephen Robertson, Hugo Zaragoza, et al. 2009. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends in Information Retrieval , 3(4):333--389
2009
-
[16]
Rulin Shao, Rui Qiao, Varsha Kishore, Niklas Muennighoff, Xi Victoria Lin, Daniela Rus, Bryan Kian Hsiang Low, Sewon Min, Wen-tau Yih, Pang Wei Koh, et al. 2025. Reasonir: Training retrievers for reasoning tasks. arXiv preprint arXiv:2504.20595
2025 arXiv
-
[17]
Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. 2023. Distilling reasoning capabilities into smaller language models. Findings of the Association for Computational Linguistics: ACL 2023, pages 7059--7073
2023
-
[18]
Hongjin Su, Howard Yen, Mengzhou Xia, Weijia Shi, Niklas Muennighoff, Han-yu Wang, Haisu Liu, Quan Shi, Zachary S Siegel, Michael Tang, et al. 2024. Bright: A realistic and challenging benchmark for reasoning-intensive retrieval. arXiv preprint arXiv:2407.12883
2024 arXiv
-
[19]
Yang Sui, Yu-Neng Chuang, Guanchu Wang, Jiamu Zhang, Tianyi Zhang, Jiayi Yuan, Hongyi Liu, Andrew Wen, Shaochen Zhong, Hanjie Chen, et al. 2025. Stop overthinking: A survey on efficient reasoning for large language models. arXiv preprint arXiv:2503.16419
2025 arXiv
-
[20]
Weiwei Sun, Lingyong Yan, Xinyu Ma, Shuaiqiang Wang, Pengjie Ren, Zhumin Chen, Dawei Yin, and Zhaochun Ren. 2023. Is chatgpt good at search? investigating large language models as re-ranking agents. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language...
2023
-
[21]
Qwen Team. 2025. https://qwenlm.github.io/blog/qwq-32b/ Qwq-32b: Embracing the power of reinforcement learning
2025
-
[22]
Nandan Thakur, Nils Reimers, Andreas R \"u ckl \'e , Abhishek Srivastava, and Iryna Gurevych. 2021. Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models. arXiv preprint arXiv:2104.08663
2021 arXiv
-
[23]
Kexin Wang, Nandan Thakur, Nils Reimers, and Iryna Gurevych. 2021. Gpl: Generative pseudo labeling for unsupervised domain adaptation of dense retrieval. arXiv preprint arXiv:2112.07577
2021 arXiv
-
[24]
Rui Wang, Hongru Wang, Boyang Xue, Jianhui Pang, Shudong Liu, Yi Chen, Jiahao Qiu, Derek Fai Wong, Heng Ji, and Kam-Fai Wong. 2025. Harnessing the reasoning economy: A survey of efficient reasoning for large language models. arXiv preprint arXiv:2503.24377
2025 arXiv
-
[25]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824--24837
2022
-
[26]
Orion Weller, Kathryn Ricci, Eugene Yang, Andrew Yates, Dawn Lawrie, and Benjamin Van Durme. 2025. Rank1: Test-time compute for reranking in information retrieval. arXiv preprint arXiv:2502.18418
2025 arXiv
-
[27]
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR)
2023
-
[28]
Shengyao Zhuang, Xueguang Ma, Bevan Koopman, Jimmy Lin, and Guido Zuccon. 2025. Rank-r1: Enhancing reasoning in llm-based document rerankers via reinforcement learning. arXiv preprint arXiv:2503.06034
2025 arXiv
-
[29]
online" 'onlinestring :=
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list...
-
[30]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.