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

Xiaochen Wang, Junqing He, Zhe Yang, Yiru Wang, Xiangdi Meng, Kunhao Pan, Zhifang SuiarXiv 2024 · OpenReview

Abstract

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.

Introduction

Multi-Hop Question Answering (MHQA) is the "detective work" of natural language processing. To answer a question like "What year was the director of 'Big Stone Gap' born?", an AI must first identify the director and then find their birth year. While Large Language Models (LLMs) excel at simple tasks, they often stumble on MHQA due to three main reasons:

  1. Error Propagation: Mistakes in early "hops" snowball into incorrect final answers.
  2. Hallucination: Complex contexts often lead LLMs to generate plausible but false information.
  3. Instruction Following: Standard Chain-of-Thought (CoT) prompting often results in messy, unparseable outputs.

Existing solutions often rely on "few-shot" prompting, which consumes context space and is expensive to scale. FSM offers a zero-shot alternative that structures reasoning as a state-based process.

The Finite State Machine (FSM) Paradigm

Instead of asking the LLM to solve a complex puzzle in a single pass, the FSM paradigm guides it through an automaton-like workflow consisting of four distinct sub-tasks:

  • Decomposer: Breaks the complex question into the first answerable sub-question.
  • Searcher: Scans the provided context to find the specific answer to that sub-question.
  • Revisor: Updates the original complex question using the newly found information, simplifying the remaining task.
  • Judge: Determines if the question is fully answered or if another iteration is required.
The FSM workflow and a concrete example of multi-hop reasoning for film release dates.

This iterative loop allows for error checking and backtracking. If a sub-answer is irregular, the model can self-revise before moving to the next step. The authors also introduced FSM2, which includes a "Final Review Step" to verify the consistency of the entire reasoning chain against the source text.

Experimental Evaluation

The method was evaluated on three high-quality MHQA benchmarks: HotpotQA (two-hop reasoning), 2WikiMultiHopQA (structured reasoning), and Musique (designed to prevent reasoning shortcuts). The researchers tested these datasets using GPT-3.5-turbo-1106 and Qwen-72B-chat.

Key Results and Insights

The quantitative improvements were substantial, particularly on the most difficult datasets. By forcing the LLM to focus on exactly one sub-task at a time, the cognitive load is reduced, preventing the model from losing track of instructions.

Performance comparison across benchmarks, highlighting FSM's superior format accuracy and F1 scores.

Performance and Reliability

On the Musique dataset, FSM1/FSM2 achieved F1 scores around 40.5–48.5, nearly doubling the performance of some baselines. The benefits were consistent across both proprietary (GPT) and open-source (Qwen) models, proving the paradigm's versatility.

Format Accuracy and Hallucination Mitigation

One of the most significant findings was the 100% format accuracy achieved by FSM. While standard CoT often failed to produce valid JSON, FSM's narrow, strictly defined output requirements for each state ensured perfect reliability for automated pipelines. Furthermore, because the model must cite specific paragraph titles and answers at each hop, it is much harder for it to hallucinate a path to a wrong answer.

Conclusion and Future Work

FSM demonstrates that a well-structured process can be more valuable than static examples. While the multi-turn dialogue process increases latency and cost per question, the gains in accuracy and reliability are significant for complex reasoning. Future directions include adapting this framework to tasks like Natural Language to SQL (NL2SQL), where step-by-step logic and strict formatting are equally critical.

Summary updated

Abstract

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.
BibTeX
@misc{wang2024fsm,
  author = {Xiaochen Wang and Junqing He and Zhe Yang and Yiru Wang and Xiangdi Meng and Kunhao Pan and Zhifang Sui},
  title = {{FSM: A Finite State Machine Based Zero-Shot Prompting Paradigm for Multi-Hop Question Answering}},
  year = {2024},
  eprint = {2407.02964},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.02964},
}
Figure