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

Dohyeon Lee, Yeonseok Jeong, Seung-won Hwang

TL;DR

Large language models (LLMs) can "overthink" in information retrieval (IR) by generating excessively long and redundant reasoning steps. This paper introduces State Machine Reasoning (SMR), a novel framework that models IR reasoning as discrete state transitions with specific actions (REFINE, RERANK, STOP). SMR significantly improves retrieval performance and drastically reduces token usage, offering a practical and efficient alternative to traditional LLM reasoning.

What Problem Does This Paper Address?

LLMs, when prompted with Chain-of-Thought (CoT), can perform complex reasoning for tasks like information retrieval (IR). However, this often leads to "overthinking," where models generate lengthy, redundant, or even incorrect reasoning steps that don't improve results and waste computational resources. Two key challenges in IR are identified: redundant trajectories (revisiting similar reasoning states) and misguided reasoning (drifting away from the user's original intent). Existing methods like compressed CoT can reduce token usage but risk misaligning outputs and require task-specific training, limiting their generalizability.

Methods

The authors propose State Machine Reasoning (SMR), a framework that reframes reasoning as a Markov Decision Process (MDP) with a discrete action space and structured state representation. Instead of token-level generation, SMR operates on structured states defined by the current query and a ranked list of retrieved documents ($S_t = (q_t, D_t)$).

The core components are:

  • Structured State Representation: Maintains the current query ($q_t$) and the ranked document list ($D_t$) to guide reasoning.
  • Stop Decision: A mechanism to detect when the system has reached an equivalent state or no meaningful gain can be achieved, enabling early stopping.
  • IR-Specific Reasoning Actions: A discrete action space consisting of:
  • REFINE: Updates the query to better reflect user intent, guided by retrieved documents. This action is followed by re-retrieval.
  • RERANK: Adjusts the ordering of the retrieved document list without changing the query.
  • STOP: Terminates the reasoning process.
  • Action Selection Policy: An LLM, guided by a structured prompt, selects the next action based on the current state, mimicking a decision-making agent. This policy is designed to be transparent and interpretable.

Datasets

The authors evaluate SMR on two benchmarks:

  • BRIGHT: A recent benchmark designed for reasoning-intensive retrieval scenarios, comprising 12 subsets across diverse domains (e.g., forums, coding, STEM Q&A). This is used as the primary benchmark.
  • BEIR: A widely-used benchmark for standard IR evaluation, covering diverse domains (e.g., factoid QA, biomedical search). This is used to assess generalizability.

Key Insights and Ideas

  • Decomposing Reasoning: Treating IR reasoning as a sequence of discrete, structured state transitions (query and document list) rather than continuous token generation is key to mitigating overthinking.
  • Action-Driven Control: The limited, IR-specific action space (REFINE, RERANK, STOP) provides fine-grained control and prevents the LLM from generating arbitrary or irrelevant text.
  • Early Stopping is Crucial: The ability to detect when further reasoning won't yield significant gains is vital for efficiency and preventing semantic drift.
  • Prompt-Based Policy: Using a prompt to guide the LLM's action selection makes the decision process transparent and adaptable without requiring task-specific training or reward engineering.
  • Generalizability: SMR's structured approach is not limited to complex reasoning tasks and shows strong performance on standard IR benchmarks as well.

Key Results

  • Improved Retrieval Performance: SMR achieves up to a 3.4% improvement in nDCG@10 on the BRIGHT benchmark compared to strong baselines.
  • Drastic Token Reduction: SMR reduces inference token usage by an average of 74.4% compared to CoT baselines, significantly outperforming even compressed CoT methods.
  • Robustness: SMR demonstrates consistent performance across different LLMs (both reasoning and non-reasoning) and retrievers (sparse and dense).
  • Action Efficiency: The policy model effectively adapts action lengths based on query complexity, with 25% of queries resolved within 3 steps and 50% within 6.
  • Intent Preservation: Refined queries maintain an average alignment score of above 0.9 with the original intent, demonstrating that iterative refinement does not lead to semantic drift.

Limitations and Future Work

  • State Representation: The current state representation is limited to the query and top-k retrieved documents. It does not incorporate user interaction signals like click-through rates or engagement metrics, which could further enhance state fidelity.
  • Action Space: While the current action space (REFINE, RERANK, STOP) is modular, future work could explore integrating additional operations like domain-specific retrieval modules or document filters.
  • Max Steps: A hard cap of 16 steps is enforced for computational constraints, but the upward trend in performance with more steps suggests potential for further gains with extended actions.

Summary updated

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.
BibTeX
@inproceedings{lee2025from,
  author = {Dohyeon Lee and Yeonseok Jeong and Seung-won Hwang},
  title = {{From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure