EvoFSM: Controllable Self-Evolution for Deep Research with Finite State Machines

Shuo Zhang, Chaofa Yuan, Ryan Guo, Xiaomin Yu, Rui Xu, Zhangquan Chen, Zinuo Li, Zhi Yang, Shuhao Guan, Zhenheng Tang, Sen Hu, Liwen Zhang, Ronghao Chen, Huacan WangarXiv 2026 · arXiv · OpenReview

TL;DR

This paper introduces EvoFSM, a novel framework for LLM-based agents that enables controllable self-evolution for complex research tasks. By structuring evolution around Finite State Machines (FSMs) and decoupling "flow" (state transitions) from "skill" (state execution), EvoFSM achieves adaptability without the instability of unconstrained rewriting, leading to significant performance improvements.

What Problem Does This Paper Address?

Large Language Model (LLM) agents have shown great potential for automating deep research. However, current approaches often rely on rigid, pre-defined workflows that struggle to adapt to the dynamic and open-ended nature of real-world research queries. While "self-evolution" methods aim to address this by allowing agents to modify their own code or prompts, these unconstrained approaches frequently lead to instability, hallucinations, and a drift from the original instructions. This paper tackles the challenge of creating LLM agents that can effectively adapt and improve their research capabilities in a controlled and reliable manner.

Methods

EvoFSM introduces a structured approach to self-evolution by modeling the research process as an explicit Finite State Machine (FSM). This FSM represents the agent's workflow, with states corresponding to specific actions (e.g., Search, Browse) and transitions defining the logic between them. The core innovation lies in decoupling the evolution process into two dimensions:

  • Flow (State-Transition Logic): This governs the macroscopic structure of the FSM, determining how the agent moves between different states. EvoFSM uses atomic operations like ADD_STATE or MODIFY_TRANSITION to dynamically reconfigure this flow.
  • Skill (State-Specific Behaviors): This refers to the microscopic capabilities within each state, defined by the agent's instructions or prompts. EvoFSM refines these skills using operations like REVISE_INSTRUCTION to improve their effectiveness.

A Critic Mechanism guides this evolution by evaluating the agent's output and identifying failure modes. This feedback triggers the Structured Self-Evolution process, which applies atomic operations to refine either the flow or the skill, or both synergistically. Furthermore, EvoFSM incorporates a Self-Evolving Memory that stores successful and failed trajectories. This memory acts as a warm-start for future tasks, providing successful strategies as priors and failure patterns as constraints to prevent repeated mistakes.

Datasets

EvoFSM is evaluated on five multi-hop question answering (QA) benchmarks:

  • HotpotQA: A large-scale dataset requiring reasoning over multiple Wikipedia paragraphs.
  • 2WikiMultihopQA (2WIKI): Provides multi-hop QA with explicit reasoning paths.
  • MuSiQue: Synthesizes 2–4 hop questions by composing evidence from single-hop datasets.
  • Bamboogle: A collection of compositional questions that are often challenging for search engines.
  • xbench-DeepSearch (Deepsearch): A Chinese-context question pool for multi-hop QA and deep search.

The paper also mentions evaluation on two interactive decision-making benchmarks: ALFWorld and WebShop.

Key Insights and Ideas

  • Structured Evolution is Key: Unconstrained self-evolution leads to instability. By imposing structure through FSMs and atomic operations, EvoFSM achieves controllable and reliable improvement.
  • Decoupling Flow and Skill: Separating the workflow logic (Flow) from the execution capabilities (Skill) allows for targeted improvements. This is crucial because some problems require changing how the agent works (flow), while others need improving what the agent can do (skill).
  • Atomic Operations for Interpretability: Using a predefined set of atomic operations makes the evolution process more interpretable and reversible, unlike free-form rewriting.
  • Memory for Continuous Learning: The self-evolving memory is vital for transferring knowledge across tasks, enabling the agent to learn from past successes and failures, leading to progressive improvement.
  • Synergy of Structure and Evolution: The combination of a stable FSM structure and dynamic, guided evolution yields greater benefits than either component alone.

Key Results

  • EvoFSM consistently outperforms baseline methods like Standard RAG, Agentic RAG, and Search-01 across all five multi-hop QA benchmarks and various LLM backbones.
  • On the challenging DeepSearch benchmark, EvoFSM achieves 58.0% accuracy with the Claude-4 backbone, a significant improvement over baselines.
  • Ablation studies show that both the structured FSM topology and the structured self-evolution mechanism are critical for performance. Removing either leads to substantial accuracy drops.
  • EvoFSM demonstrates strong generalization capabilities on interactive decision-making tasks like ALFWorld and WebShop, outperforming methods like ReAct and Reflexion.
  • The number of evolution iterations positively correlates with accuracy, especially on complex tasks like DeepSearch, suggesting that deeper refinement leads to better performance.

Limitations and Future Work

The authors acknowledge several limitations:

  • Reliance on Off-the-Shelf LLMs: EvoFSM currently uses proprietary LLMs via prompt engineering and in-context learning, without fine-tuning. This limits efficiency and responsiveness, as general-purpose models may not fully internalize complex FSM logic. Future work could involve distilling self-evolving capabilities into smaller, specialized agents.
  • Critic Mechanism Reliability: The entire self-evolving process depends on the Critic Mechanism to accurately diagnose failures. If the Critic hallucinates or misses subtle errors, the system might learn incorrect patterns. Developing more robust, verification-guided critics is an open challenge.
  • Memory Scalability: The self-evolving memory grows indefinitely, potentially leading to retrieval latency and the inclusion of redundant or outdated strategies. Future work should focus on implementing a long-term memory management system for consolidation and forgetting.

Summary updated

Abstract

While LLM-based agents have shown promise for deep research, most existing approaches rely on fixed workflows that struggle to adapt to real-world, open-ended queries. Recent work therefore explores self-evolution by allowing agents to rewrite their own code or prompts to improve problem-solving ability, but unconstrained optimization often triggers instability, hallucinations, and instruction drift. We propose EvoFSM, a structured self-evolving framework that achieves both adaptability and control by evolving an explicit Finite State Machine (FSM) instead of relying on free-form rewriting. EvoFSM decouples the optimization space into macroscopic Flow (state-transition logic) and microscopic Skill (state-specific behaviors), enabling targeted improvements under clear behavioral boundaries. Guided by a critic mechanism, EvoFSM refines the FSM through a small set of constrained operations, and further incorporates a self-evolving memory that distills successful trajectories as reusable priors and failure patterns as constraints for future queries. Extensive evaluations on five multi-hop QA benchmarks demonstrate the effectiveness of EvoFSM. In particular, EvoFSM reaches 58.0% accuracy on the DeepSearch benchmark. Additional results on interactive decision-making tasks further validate its generalization.
BibTeX
@misc{zhang2026evofsm,
  author = {Shuo Zhang and Chaofa Yuan and Ryan Guo and Xiaomin Yu and Rui Xu and Zhangquan Chen and Zinuo Li and Zhi Yang and Shuhao Guan and Zhenheng Tang and Sen Hu and Liwen Zhang and Ronghao Chen and Huacan Wang},
  title = {{EvoFSM: Controllable Self-Evolution for Deep Research with Finite State Machines}},
  year = {2026},
  eprint = {2601.09465},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.09465},
}
Figure