From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval (2025)

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 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.

## introduction chain-of-thought (cot) prompting @xcite has emerged as a powerful paradigm for enhancing large language model (llm) reasoning across complex tasks @xcite such as math and planning. this paper focuses on extending cot-based reasoning to information retrieval (ir) @xcite , to better align retrieval with user intent for improved query rewriting @xcite and document reranking @xcite . despite its strengths, cot prompting often suffers from overthinking @xcite @xcite -the generation of semantically redundant or incorrect reasoning steps that offer no benefit and may even be detrimental. ## proposed method our framework can be viewed as a markov decision process (mdp) with a discrete action space and structured state representation. while we do not explicitly learn a value function, our design is inspired by decision-theoretic frameworks @xcite , where each reasoning step corresponds to a transition between abstract states. based on this formulation, we recast reasoning as transitions over ir-specific states and actions, rather than as token-level generation. ## conclusion we presented smr, a structured reasoning for retrieval by modeling reasoning as transitions over discrete states, defined as queries and document rankings. to mitigate overthinking, unlike prior methods such as cot prompting or react relying on token-level generation or tool calls, smr takes an action-driven approach constraining reasoning to a set of ir-specific actions and grounding each step in a well-defined state. smr offers a compact and controllable alternative to token-level reasoning with three key benefits: (1) improved retrieval performance, (2) reduced token usage through early stopping and redundancy checks, and (3) robust generalization across retrievers and llms without task-specific tuning. experiments on the bright and beir benchmarks validate these advantages, with smr outperforming strong baselines in both complex and standard ir settings.