DFA-RAG: Conversational Semantic Router for Large Language Model with Definite Finite Automaton

Yiyou Sun, Junjie Hu, Wei Cheng, Haifeng Chen

The Challenge of Controlling LLMs

While Large Language Models (LLMs) like GPT-4 are incredibly versatile, they are notoriously difficult to "control" in professional settings. In industries like customer service, healthcare, or technical support, a chatbot cannot simply be creative; it must follow specific policies, verify information in a certain order, and adhere to a predetermined workflow.

Standard Retrieval-Augmented Generation (RAG) helps by providing external context, but it often treats dialogues as flat chunks of text. It struggles to understand the trajectory of a conversation—where the user is in a multi-step process. Consequently, standard LLMs often go "off-rails," providing inappropriate or out-of-sequence responses. Fine-tuning is a common fix, but it requires massive datasets, risks overfitting, and makes the model brittle to minor changes in policy.

Introducing DFA-RAG

To address these limitations, researchers propose DFA-RAG, a novel framework that embeds a structured "map" of conversational possibilities directly into the RAG process. By mapping dialogues to a human-readable state machine, the framework ensures that AI agents remain compliant and contextually accurate without the need for expensive fine-tuning.

The DFA-RAG framework illustrating how dialogue history maps to a DFA state machine to guide LLM responses.

The DFA-RAG system operates through a clear, multi-step pipeline:

  1. Tag Extraction: Instead of using raw text, the system uses an LLM to distill every utterance into a set of concise "tags" (e.g., "How can I help?" becomes #issue).
  2. DFA Construction: These tag sequences are used to build a Definite Finite Automaton (DFA)—a state machine where each node represents a specific stage in a conversation (e.g., "Identifying the problem" or "Providing a solution").
Algorithm and process for building the initial tree-like DFA from extracted tag sequences.
  1. State Merging: To prevent the DFA from becoming an unmanageable "bushy" tree, the authors introduce a similarity score to merge states that lead to similar outcomes, keeping the structure lean and efficient.
  2. The Semantic Router: During a live chat, the system tags the user's input and "navigates" the DFA to find the current state. It then retrieves historical dialogue examples associated with that exact state.
  3. Guided Generation: These state-specific examples are fed into the LLM prompt, effectively "routing" the model to generate a response that fits the current stage of the workflow.

Key Insights and Advantages

  • Interpretability is a Feature: Unlike standard RAG, which relies on "black box" vector embeddings, the DFA is human-readable. A developer can look at the graph and see exactly why a bot chose a specific path.
  • Granular vs. Global Retrieval: Most RAG systems retrieve similar documents. DFA-RAG retrieves similar moments. By focusing on the specific state in the workflow, the retrieved examples are functionally relevant, not just semantically similar.
  • Handling the "Out-of-Distribution" (OOD) Problem: If a user says something the DFA doesn't recognize, the system doesn't crash. It reverts to the last known valid state, allowing the LLM to use its general intelligence to handle the query while staying as close to the "rails" as possible.
  • Plug-and-Play: The system doesn't require training a new model. It works with existing LLMs (like GPT-3.5 or GPT-4) as a logic layer sitting on top of them.

Performance and Results

The researchers evaluated DFA-RAG across diverse customer service domains, including Twitter-based support (AmazonHelp, AskPlayStation, etc.) and the MultiWOZ benchmark for complex, goal-oriented conversations.

Using a "Win Rate" metric where GPT-4 acted as a judge, DFA-RAG achieved an average win rate of 74.3% (with GPT-4) and 75.9% (with GPT-3.5), consistently outperforming standard RAG, BM25 retrieval, and random sampling. In many cases, DFA-RAG even outperformed fine-tuned models, proving that structured retrieval can be more effective than weight updates for following workflows. Furthermore, on the MultiWOZ dataset, DFA-RAG achieved a 90.0% Success Rate, nearly matching models that had access to "ground truth" state information.

Limitations and Future Work

While highly effective, DFA-RAG has a few limitations. The quality of the DFA depends entirely on the LLM's ability to extract accurate tags; noisy initial tagging will result in a flawed state machine. Additionally, the DFA is currently learned once from a static training set. Future iterations could allow the DFA to "evolve" in real-time as new conversational patterns emerge. Finally, while state merging helps, extremely complex domains with hundreds of overlapping variables might still result in large DFAs that are difficult for humans to audit manually.

Summary updated

Abstract

This paper introduces the retrieval-augmented large language model with Definite Finite Automaton (DFA-RAG), a novel framework designed to enhance the capabilities of conversational agents using large language models (LLMs). Traditional LLMs face challenges in generating regulated and compliant responses in special scenarios with predetermined response guidelines, like emotional support and customer service. Our framework addresses these challenges by embedding a Definite Finite Automaton (DFA), learned from training dialogues, within the LLM. This structured approach acts as a semantic router which enables the LLM to adhere to a deterministic response pathway. The routing is achieved by the retrieval-augmentation generation (RAG) strategy, which carefully selects dialogue examples aligned with the current conversational context. The advantages of DFA-RAG include an interpretable structure through human-readable DFA, context-aware retrieval for responses in conversations, and plug-and-play compatibility with existing LLMs. Extensive benchmarks validate DFA-RAG's effectiveness, indicating its potential as a valuable contribution to the conversational agent.
BibTeX
@inproceedings{sun2024dfa,
  author = {Yiyou Sun and Junjie Hu and Wei Cheng and Haifeng Chen},
  title = {{DFA-RAG: Conversational Semantic Router for Large Language Model with Definite Finite Automaton}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=LpAzlcGzJ6},
}
Figure