# State Machine of Thoughts: Leveraging Past Reasoning Trajectories for Enhancing Problem Solving

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

## Key facts

- Cited by 4 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 0 of its 23 references that are in the map.
- First posted on arXiv 29 Dec 2023.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Built on by (most cited first, 4 of 4)

- [MetaAgent: Automatically Constructing Multi-Agent Systems Based on Finite State Machines](https://mlsanity.com/paper/2507.22606/) (2025)
- [EmoFSM: A Finite State Machine for Emotional Support Conversation](https://mlsanity.com/paper/2504.11837/) (2025)
- [PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM Agents](https://mlsanity.com/paper/2608.19861/) (2026)
- [From Token to Action: State Machine Reasoning to Mitigate Overthinking in Information Retrieval](https://mlsanity.com/paper/2505.23059/) (2025)

## Abstract (arXiv)

Current Large Language Model-based agents reason within an exploration-evaluation framework, navigating problem-solving processes in a tree-like manner. However, these methods often neglect successful reasoning trajectories once a problem is resolved, leading to inefficient use of these trajectories for future analogous problems. To address this inefficiency, we adopt a state machine to record experience derived from previous reasoning trajectories. Within the state machine, states represent decomposed sub-problems, while state transitions reflect the dependencies among sub-problems. The state machine records both successful and failed trajectories. Utilizing the experience from the state machine, our proposed State Machine of Thoughts (SMoT) selects the most optimal sub-solutions and avoids incorrect ones. Our experiments show that SMoT can significantly improve problem-solving abilities in two exploration-intensive problems: the 24-point game and a taxi navigation reinforcement learning game.