Abstract
Large Language Models (LLMs) often struggle to adhere to specific professional workflows or policies in task-oriented dialogues. This paper introduces DFA-RAG, a framework that integrates a Definite Finite Automaton (DFA) as a semantic router to guide LLM responses. By mapping conversations to a state machine learned from historical data, DFA-RAG ensures contextually relevant and policy-compliant interactions. Experimental results across multiple domains, including customer service and MultiWOZ, demonstrate that DFA-RAG outperforms standard Retrieval-Augmented Generation (RAG) and fine-tuning approaches in both win rate and task success.
Introduction
While Large Language Models like GPT-4 are incredibly versatile, they are often "unruly" in professional settings. In industries like customer service or healthcare, a chatbot must follow a specific policy or workflow (e.g., "Ask for the system version before suggesting a fix"). Standard LLMs often deviate from these guidelines or hallucinate inappropriate steps.
Traditional fixes like fine-tuning are data-hungry and expensive, while standard Retrieval-Augmented Generation (RAG) often struggles to pick the right historical examples because it prioritizes semantic similarity over the actual stage of the conversation. DFA-RAG aims to bridge the gap between the flexibility of LLMs and the reliability of rule-based systems.
The DFA-RAG Framework
The authors propose DFA-RAG, a framework that treats a conversation like a traversal through a state machine. The process involves three main phases: learning the map, semantic routing, and guided generation.
1. Learning the Map (DFA Construction)
The DFA is constructed through a systematic pipeline that transforms unstructured dialogue into a structured state machine:
- Tagging: An LLM processes training dialogues to extract concise "tags" (e.g.,
#battery,#issue). - Tree Building: These tag sequences are organized into a prefix tree where each node represents a state in a conversation.
- State Merging: To prevent the tree from becoming too complex, the authors use a similarity score to merge states that lead to similar future outcomes, resulting in a human-readable DFA.
2. The Semantic Router and Guided Generation
During inference, the system tags the user's input and navigates the DFA to identify the current "state." Each state maintains a record of training dialogues that passed through it. The system then retrieves five example dialogues from the current state and feeds them into the LLM as part of a few-shot prompt. This ensures the LLM sees examples of how a human agent handled the exact stage of the workflow.
Experimental Evaluation
The researchers evaluated DFA-RAG across six diverse domains:
- Twitter-based Customer Service: Five datasets (AmazonHelp, DeltaSupport, AskPlayStation, AirbnbHelp, NikeSupport) ranging from 1K to 50K dialogues.
- MultiWOZ (CambridgeInfo): A complex, multi-domain dataset for task-oriented dialogue evaluation, featuring longer conversations averaging 13.5 rounds.
Results and Insights
DFA-RAG demonstrated significant improvements over baseline methods:
- Superiority over RAG: DFA-RAG outperformed standard RAG by approximately 4% in win rate across both GPT-3.5 and GPT-4 backbones.
- Beating Fine-Tuning: On the NikeSupport dataset, DFA-RAG (using GPT-3.5) achieved a 70.1% win rate, significantly higher than a fine-tuned version of the same model (56.8%).
- Task Success: On the MultiWOZ benchmark, DFA-RAG achieved a 90.0% Success Rate, rivaling specialized models with access to ground-truth state information.
Key insights include the importance of functional context over semantic similarity and the interpretability of the DFA. Unlike "black-box" neural retrievers, the DFA allows developers to visualize the conversation flow. Furthermore, the system handles "unknown" inputs by reverting to the last known valid state, leveraging the LLM's natural reasoning.
Conclusion
DFA-RAG provides a robust method for grounding LLMs in structured workflows without sacrificing their inherent flexibility. While the system is dependent on the quality of initial tagging and faces visualization challenges for complex looping structures, it offers a scalable "plug-and-play" solution for professional chatbot applications. Future work will explore integration with external APIs and refining the handling of unpredictable user behavior.
Summary updated