# FSM: A Finite State Machine Based Zero-Shot Prompting Paradigm for Multi-Hop Question Answering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 14 of its 21 references that are in the map.
- First posted on arXiv 3 Jul 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 14 of 14)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Unsupervised Question Decomposition for Question Answering](https://mlsanity.com/paper/2002.09758/) (2020)
- [Compositional Questions Do Not Necessitate Multi-hop Reasoning](https://mlsanity.com/paper/1906.02900/) (2019)
- [Hierarchical Graph Network for Multi-hop Question Answering](https://mlsanity.com/paper/1911.03631/) (2019)
- [Answering Complex Open-domain Questions Through Iterative Query Generation](https://mlsanity.com/paper/1910.07000/) (2019)
- [Multi-hop Reading Comprehension across Multiple Documents by Reasoning over Heterogeneous Graphs](https://mlsanity.com/paper/1905.07374/) (2019)
- [Decomposing Complex Questions Makes Multi-Hop QA Easier and More Interpretable](https://mlsanity.com/paper/2110.13472/) (2021)
- [Self-prompted Chain-of-Thought on Large Language Models for Open-domain Multi-hop Reasoning](https://mlsanity.com/paper/2310.13552/) (2023)
- [Identifying Supporting Facts for Multi-hop Question Answering with Document Graph Networks](https://mlsanity.com/paper/1910.00290/) (2019)

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

- [Convert Language Model into a Value-based Strategic Planner](https://mlsanity.com/paper/2505.06987/) (2025)
- [Evaluation Hallucination in Multi-Round Incomplete Information Lateral-Driven Reasoning Tasks](https://mlsanity.com/paper/2505.23843/) (2025)
- [Dream to Chat: Model-based Reinforcement Learning on Dialogues with User Belief Modeling](https://mlsanity.com/paper/2508.16876/) (2025)
- [Codified Finite-state Machines for Role-playing](https://mlsanity.com/paper/2602.05905/) (2026)
- [An Agentic Flow for Finite State Machine Extraction using Prompt Chaining](https://mlsanity.com/paper/2507.11222/) (2025)
- [Making Language Model a Hierarchical Classifier](https://mlsanity.com/paper/2507.12930/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) with chain-of-thought (COT) prompting have demonstrated impressive abilities on simple nature language inference tasks. However, they tend to perform poorly on Multi-hop Question Answering (MHQA) tasks due to several challenges, including hallucination, error propagation and limited context length. We propose a prompting method, Finite State Machine (FSM) to enhance the reasoning capabilities of LLM for complex tasks in addition to improved effectiveness and trustworthiness. Different from COT methods, FSM addresses MHQA by iteratively decomposing a question into multi-turn sub-questions, and self-correcting in time, improving the accuracy of answers in each step. Specifically, FSM addresses one sub-question at a time and decides on the next step based on its current result and state, in an automaton-like format. Experiments on benchmarks show the effectiveness of our method. Although our method performs on par with the baseline on relatively simpler datasets, it excels on challenging datasets like Musique. Moreover, this approach mitigates the hallucination phenomenon, wherein the correct final answer can be recovered despite errors in intermediate reasoning. Furthermore, our method improves LLMs' ability to follow specified output format requirements, significantly reducing the difficulty of answer interpretation and the need for reformatting.