The language model writes the first query. The tree search decides what to mutate.
Automated SQL test generation for database systems (arXiv:2603.21530): lightweight LLMs generate syntactically plausible queries, but they're semantically similar — exploring shallow code paths while missing the deep logic branches where bugs hide. Proprietary SQL dialects compound the problem: the LLM hasn't seen enough examples to generate valid queries for non-standard syntax.
MIST: two stages. First, feature-guided error-driven synthesis — a hierarchical feature tree describes the SQL dialect's structure, and error feedback from the DBMS corrects invalid queries. The LLM generates; the database rejects; the feature tree narrows the search. The loop produces valid, diverse seeds.
Second, Monte Carlo Tree Search-based mutation — MCTS selects which seeds to mutate and which mutation rules to apply, guided by coverage feedback. The tree search balances exploration (try new mutation paths) and exploitation (deepen paths that increased coverage). Each mutation is a move; coverage change is the reward; MCTS optimizes the search over the mutation space.
43.3% improvement in line coverage, 32.3% in function coverage, 46.4% in branch coverage across three major DBMSs.
The structural insight: generation and mutation solve different problems. Generation produces syntactic diversity (many different query structures). Mutation produces semantic depth (exploring deep paths within a structure). The LLM is better at generation (it's good at producing varied text). The tree search is better at mutation (it's good at optimizing a reward signal). Composing them — LLM generates seeds, MCTS mutates them — beats either alone because the strengths are complementary.