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

Xiaochen Wang, Junqing He, Liang Chen, Reza Haf, Zhe Yang, Yiru Wang, Xiangdi Meng, Kunhao Pan, Zhifang Sui

Abstract

Large Language Models with chain-of-thought prompting, such as OpenAI-o1, have shown impressive capabilities in natural language inference tasks. However, Multi-hop Question Answering (MHQA) remains challenging for many existing models due to issues like hallucination, error propagation, and limited context length. To address these challenges and enhance LLMs' performance on MHQA, we propose the Self-Guiding prompting Finite State Machine (SG-FSM), designed to strengthen multi-hop reasoning abilities. Unlike traditional chain-of-thought methods, SG-FSM tackles MHQA by iteratively breaking down complex questions into sub-questions, correcting itself to improve accuracy. It processes one sub-question at a time, dynamically deciding the next step based on the current context and results, functioning much like an automaton. Experiments across various benchmarks demonstrate the effectiveness of our approach, outperforming strong baselines on challenging datasets such as Musique. SG-FSM reduces hallucination, enabling recovery of the correct final answer despite intermediate errors. It also improves adherence to specified output formats, simplifying evaluation significantly.

Introduction

Multi-hop Question Answering (MHQA) represents a significant hurdle in natural language processing, requiring models to synthesize information across multiple documents to reach a conclusion. While Large Language Models (LLMs) have excelled in many reasoning tasks, they often struggle with the "lost-in-the-middle reasoning path" in MHQA. This phenomenon occurs when long reasoning chains lead to rationale drift, where early errors propagate, or focus loss, where the model loses track of the original query. Furthermore, complex reasoning often results in format mismatches, complicating automated evaluation.

To overcome these limitations, the Self-Guiding prompting Finite State Machine (SG-FSM) framework introduces a structured, zero-shot prompting paradigm that models the reasoning process as a formal automaton.

The SG-FSM Framework

The core of SG-FSM is the conceptualization of multi-hop reasoning as a Finite State Machine (FSM). Instead of a linear, unconstrained chain of thought, the model is guided through a series of discrete states, each with specific responsibilities.

The SG-FSM architecture models the reasoning process as a state machine, transitioning between decomposition, searching, and revision states to ensure accuracy and format adherence.

The framework operates in two primary phases:

  1. SG-FSM1 (Iterative Solving): The model functions as an automaton, moving between states such as Decomposing (breaking down the complex question), Searching (retrieving sub-answers), and Revising (correcting format or logical inconsistencies). This modularity prevents the model from being overwhelmed by complex, multi-part instructions.
  2. SG-FSM2 (Summarization): After gathering all necessary evidence, a final summarization state reviews the sub-answers and context to produce a verified final response.

A key feature is the Revisor state. If the model detects an "illegal" output format (e.g., malformed JSON), it triggers a self-correction loop. This ensures near 100% adherence to specified output formats, a common failure point for standard prompting methods.

Experimental Evaluation

The researchers evaluated SG-FSM against three major MHQA benchmarks: HotpotQA (2-hop), 2WikiMultiHopQA (structured reasoning), and Musique (complex 2-4 hop reasoning). The experiments utilized both GPT-3.5-turbo and Qwen-72B models.

Performance comparison of SG-FSM against Direct and CoT prompting across Musique, HotpotQA, and 2WikiQA benchmarks.

The results, summarized in the table above, highlight several key findings:

  • Significant Gains on Musique: On the most challenging dataset, Musique, SG-FSM nearly doubled the F1 score for the Qwen-72B model (from 24.0 to 48.5).
  • Robustness Across Models: Even the smaller GPT-3.5 model using SG-FSM outperformed larger models using traditional Chain-of-Thought (CoT) prompting.
  • Error Recovery: By evaluating whether to "continue" after each hop, the framework allows the model to recover from intermediate reasoning failures that would typically derail a standard CoT prompt.

Conclusion and Future Work

SG-FSM demonstrates that imposing formal structure on LLM reasoning can significantly mitigate common issues like hallucination and format drift in multi-hop tasks. By treating reasoning as a state-managed process, the framework provides a more reliable and explainable path to the final answer.

However, the multi-turn nature of SG-FSM introduces higher inference latency and cost compared to single-shot methods. Future research may explore integrating this FSM-based control logic directly into the model's training or fine-tuning phases to achieve similar robustness with reduced overhead.

Summary updated

Abstract

Large Language Models with chain-of-thought prompting, such as OpenAI-o1, have shown impressive capabilities in natural language inference tasks. However, Multi-hop Question Answering (MHQA) remains challenging for many existing models due to issues like hallucination, error propagation, and limited context length. To address these challenges and enhance LLMs' performance on MHQA, we propose the Self-Guiding prompting Finite State Machine (SG-FSM), designed to strengthen multi-hop reasoning abilities. Unlike traditional chain-of-thought methods, SG-FSM tackles MHQA by iteratively breaking down complex questions into sub-questions, correcting itself to improve accuracy. It processes one sub-question at a time, dynamically deciding the next step based on the current context and results, functioning much like an automaton. Experiments across various benchmarks demonstrate the effectiveness of our approach, outperforming strong baselines on challenging datasets such as Musique. SG-FSM reduces hallucination, enabling recovery of the correct final answer despite intermediate errors. It also improves adherence to specified output formats, simplifying evaluation significantly.
BibTeX
@inproceedings{wang2025sg,
  author = {Xiaochen Wang and Junqing He and Liang Chen and Reza Haf and Zhe Yang and Yiru Wang and Xiangdi Meng and Kunhao Pan and Zhifang Sui},
  title = {{SG-FSM: A Self-Guiding Zero-Shot Prompting Paradigm for Multi-Hop Question Answering Based on Finite State Machine}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2025},
  url = {https://openreview.net/forum?id=261hsk6PcG},
}
Figure