💬 NLP

LLM-Driven Multi-Turn Task-Oriented Dialogue Synthesis for Realistic Reasoning

This paper proposes an LLM-driven framework that utilizes trilevel optimization to synthesize realistic, multi-turn task-oriented dialogues and iteratively refined reasoning tasks, thereby addressing the limitations of existing benchmarks in evaluating and enhancing the logical reasoning capabilities of large language models.

Original authors: Yu Zhu, Kai Yang

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yu Zhu, Kai Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to solve a real-world mystery, like figuring out why a flight was delayed or calculating the best travel reimbursement.

For a long time, scientists have tested these robots (Large Language Models, or LLMs) using textbook puzzles. These puzzles are like math problems on a whiteboard: clean, clear, and having only one right answer. But in the real world, life isn't a whiteboard. It's messy, full of hidden clues, conflicting rules, and long conversations.

This paper introduces a new way to build a training gym for these robots, specifically designed to make them better at "real-life" reasoning. Here is how they did it, broken down into simple concepts:

1. The Problem: The "Video Game" vs. The "Real World"

Currently, most tests for AI are like playing a video game where the rules are written in the instructions. The AI just needs to follow the script.

The Issue: In the real world, you don't get a script. You have to remember what you said five minutes ago, check a website for a rule, and realize that a "business trip" has different rules than a "vacation."
The Result: Current AI models are great at the video game but often fail when the situation gets messy and requires deep thinking.

2. The Solution: The "Method Actor" Approach

Instead of just asking the AI to "solve a problem," the authors created a system where the AI acts out a role.

The User Agent (The Method Actor): Imagine an actor who is hired to play a specific character, like "a stressed business traveler." Before the scene starts, this actor is given a secret backstory, a specific goal, and a list of things they need to do (like "check the weather," "call the bank," "look up the policy"). The actor then simulates doing these things, building a memory of their actions.
The Assistant Agent (The Detective): This is the AI trying to help. It talks to the "Method Actor." Because the actor has a rich, simulated history of actions, the conversation becomes deep and complex. The AI has to listen carefully, remember the actor's past actions, and use logic to figure out the answer.

The Analogy: It's the difference between asking a student, "What is 2+2?" (Textbook) vs. asking them to play a role in a courtroom drama where they have to figure out the truth based on conflicting witness testimonies and hidden evidence (Real-world).

3. The "Trilevel Optimization": The Self-Improving Coach

Building a good test is hard. If the test is too easy, the AI passes without learning. If it's too hard, the AI gives up.
The authors created a three-layer coaching system (Trilevel Optimization) to automatically fix the tests:

Level 1 (The Question): The coach looks at the questions being asked. Are they too simple?
Level 2 (The Conversation): The coach looks at the dialogue. Is it natural? Does it flow?
Level 3 (The Scoring): The coach invents a new way to grade the conversation to see if it's actually challenging.

The Analogy: Imagine a video game developer who wants to make a level that is "just right."

They play the level (Level 1).
They watch how players move through it (Level 2).
They tweak the difficulty settings and the scoring rules (Level 3) to ensure the game is neither boring nor impossible.
Then, they do it all over again automatically, over and over, until the level is perfect.

4. The Result: "RealReasoning"

Using this method, they built a new dataset called RealReasoning.

It contains 500 complex conversations.
It includes tasks like "Math Word Problems" (calculating costs based on a story) and "Common-Sense Reasoning" (figuring out if a travel expense is valid based on unwritten rules).
They used a "filter" to remove the easy questions. If an AI could solve it instantly, they threw it away and made a harder version.

5. What They Found

When they tested current top-tier AI models on this new dataset:

The Shock: Even the smartest AIs struggled. They got about 50% right on average.
The Insight: Models that are forced to "think step-by-step" (like a human solving a puzzle on paper) did much better than those that just guess the answer immediately.
The Takeaway: We are still far from having AI that can truly reason through messy, real-life situations. We need more training data that feels like real life, not just a textbook.

Summary

The authors built a simulated reality where AI agents play roles, make mistakes, and have complex conversations. They then used a self-correcting coach to ensure these conversations are the perfect level of difficulty. The result is a new benchmark that proves: Current AI is good at following instructions, but it still needs to learn how to think like a human in a chaotic, real-world environment.

1. Problem Statement

The paper addresses the critical gap between the logical reasoning capabilities of Large Language Models (LLMs) and the complexity of real-world scenarios. Existing benchmarks and reasoning datasets suffer from three main limitations:

Oversimplification: Current datasets are often abstract, lacking the multi-source information, business rules, and long-sequence coherence required in realistic task flows.
Data Contamination: Overlap between pre-training corpora and test sets undermines the reliability of evaluation results.
Scalability and Cost: Traditional crowdsourcing for dataset construction is labor-intensive, expensive, and difficult to scale, while existing agent-based methods often rely on rigid, pre-defined schemas that fail to capture complex, emergent reasoning.

The authors aim to develop a method to synthesize high-fidelity, multi-turn, task-oriented dialogues grounded in realistic scenarios to better evaluate and enhance LLM reasoning.

2. Methodology

The proposed framework utilizes LLM agents to simulate realistic user behaviors and interactions, structured around a Trilevel Optimization process.

A. Agent-Based Dialogue Generation

The system simulates a realistic interaction between a User Agent and an Assistant Agent:

User Generator: An LLM generates diverse user profiles (roles, intents, problems) based on a specific realistic scenario description.
Simulated Actions: The User Agent does not jump straight to dialogue. Instead, it simulates a sequence of actions (e.g., searching for information, making decisions) based on external knowledge (retrieved via tools like Bing) and its internal memory (intent + action history). This creates a stable, coherent "action trajectory."
Dialogue Interaction: The User Agent engages in a multi-turn dialogue with an Assistant Agent. The User asks questions derived from its action sequence, and the Assistant reasons using external context to respond. This ensures the dialogue contains implicit logical structures that require reasoning to uncover.

B. Trilevel Optimization Framework

To ensure high quality without human intervention at every step, the authors formulate the generation and evaluation process as a Trilevel Optimization problem:

Level 1 (Metric Optimization): Optimizes the evaluation metric ( $\omega$ ) itself. Since dialogue quality metrics are discrete, an evolutionary algorithm is used to search for the best combination of base metrics (e.g., distinct-n, coherence scores) represented as a computational graph.
Level 2 (Multi-turn Prompt Optimization): Optimizes the prompt parameters ( $\theta$ ) controlling the multi-turn dialogue generation to maximize the Level 1 metric.
Level 3 (Single-turn Prompt Optimization): Optimizes the prompt parameters ( $\phi$ ) for individual turns to ensure local response quality.

Optimization Technique: Since the underlying LLMs are closed-source black boxes (no gradient access), the authors employ Zeroth-Order Optimization (using two-point estimates with random perturbations) to approximate gradients for prompt parameters, and an Evolutionary Algorithm to optimize the metric structure.

C. Iterative Dataset Refinement

The resulting dataset, RealReasoning, undergoes an iterative update process:

Difficulty Assessment: Multiple reasoning models solve the generated tasks.
Filtering: Tasks solved correctly by all models (easy) are identified. Tasks with low accuracy (difficult) are stored in a "Difficult Problem Knowledge Base."
Regeneration: New problems are generated by combining existing dialogues with difficult problems from the knowledge base, replacing the "easy" instances. This process continues until the proportion of simple problems is minimized.

3. Key Contributions

Trilevel Optimization for Synthesis: The paper formalizes dialogue generation as a trilevel optimization problem, jointly optimizing evaluation metrics and prompt designs. This enables the automatic, iterative refinement of synthetic dialogue quality without heavy reliance on human evaluators.
RealReasoning Dataset: The authors present a new dataset of 500 multi-turn, task-oriented dialogues. Each instance includes a reasoning question derived from the dialogue context and a manually verified ground-truth label. The dataset covers Math Word Reasoning (59%) and Common-Sense Reasoning (41%).
Agent-Driven Realism: By simulating user action sequences and memory before dialogue, the method generates interactions with high contextual coherence and realistic logical dependencies, overcoming the limitations of schema-based generation.
Empirical Evidence of Reasoning Gaps: The study demonstrates that even advanced LLMs struggle with these realistic reasoning tasks, validating the dataset's utility as a challenging benchmark.

4. Experimental Results

The authors evaluated the RealReasoning dataset against various LLMs (Qwen series, DeepSeek series) and compared performance against standard benchmarks (GSM8K, CODAH).

Performance Gap: Even strong models like Qwen-Plus achieved only 48.4% accuracy on the dataset without explicit reasoning prompts.
Impact of Reasoning Mechanisms: Models equipped with "thinking" or reflection mechanisms (e.g., Qwen-Plus-Thinking, DeepSeek-R1) showed significant improvements, with DeepSeek-R1 reaching 87.8% overall accuracy. This highlights the necessity of explicit reasoning processes for complex tasks.
Task Difficulty: Common-sense reasoning proved significantly harder (85.3% max accuracy for DeepSeek-R1) than Math word reasoning, suggesting current models struggle to leverage implicit internal knowledge compared to explicit external information.
Quality Metrics: The trilevel optimization framework significantly improved dialogue quality. The optimized method achieved an average score of 4.01 (out of 5) across Coherence, Fluency, and Diversity, outperforming unoptimized baselines and standard metrics like distinct-N.
Diversity: The method produced dialogues with lower semantic similarity (0.827 vs. 0.921 for direct interaction) and more diverse topic distributions, confirming the effectiveness of the action-sequence simulation.

5. Significance

This work provides a scalable, automated pipeline for creating high-quality reasoning benchmarks that reflect the complexity of real-world interactions.

Benchmarking: It offers a rigorous testbed for evaluating the "realistic" reasoning capabilities of LLMs, moving beyond abstract puzzles.
Methodological Advance: The introduction of zeroth-order trilevel optimization for dialogue generation sets a new standard for automated data synthesis, reducing the dependency on costly human annotation.
Future Direction: The results indicate that while LLMs are improving, there is still a significant gap in handling complex, multi-step reasoning in realistic contexts, guiding future research toward better reasoning architectures and training data.

Dataset Availability: The RealReasoning dataset and code are available at https://github.com/adventureoflingke/RealReasoning/.