Towards Effective Structured Context Modeling for Conversational Recommender Systems via Dual-node Monte Carlo Tree Search¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/SCUNLP/DREAMS
Area: LLM Reasoning
Keywords: Conversational Recommender Systems, Monte Carlo Tree Search, Structured Context Modeling, Preference Tracking, Strategic Dialogue Planning
TL;DR¶
Addressing the vulnerability where unstructured free-form context induces severe preference tracking errors and noisy retrieval in conversational recommenders, this paper proposes DREAMS—a unified dual-node Monte Carlo Tree Search framework that explicitly navigates structured dialogue states for strategic preference elicitation (ELNode) and adaptive query refinement (EXNode).
Background & Motivation¶
Conversational Recommender Systems (CRSs) aim to actively uncover user preferences through multi-turn dialogue (preference elicitation) while leveraging accumulated constraints to retrieve and recommend relevant items (preference exploitation). Throughout real-world multi-turn interactions, user preference signals are naturally sparse, implicit, and revealed incrementally across turns. For example, a user commenting on a movie recommendation may casually remark, "It was okay, but I'm not a big fan of Spike Lee's style." Such negative preference expresses a critical semantic constraint that must be retained across future dialogue turns to systematically suppress items associated with that director. However, prevalent LLM-based CRSs uniformly model dialogue context as unstructured free-form text, which frequently fails to preserve implicit constraints within lengthy conversational histories and causes systems to repeatedly make redundant inquiries or prematurely recommend items that users explicitly dislike.
A deeper analysis of these systemic failures reveals a twofold limitation in existing context modeling paradigms. On the preference elicitation front, directly feeding entire free-form conversation histories into LLM prompts leads to severe cognitive overload, depriving the model of calibrated foresight regarding dialogue timing—such as when to ask clarifying questions, which specific attribute to probe, and when to transition to recommendation. On the preference exploitation front, encoding raw, free-form conversational context into dense embeddings for item retrieval injects substantial conversational chatter and obsolete feedback into query representations; this noise frequently misleads dense index matching, causing preference exploitation error rates (PE²) to exceed 20% even when complete user preferences are present in the context. Recent efforts attempt to mitigate these deficiencies through JSON-based state tracking or Monte Carlo Tree Search (MCTS). Yet, JSON-based approaches (such as RA-CRS) treat each turn as an isolated static snapshot that overlooks conversational dependencies, while generic MCTS methods (such as SAPIENT and T-EPL) operate over ungrounded free-form nodes and restrict tree search exclusively to the elicitation phase.
Consequently, neither paradigm enables effective, end-to-end user preference tracking. To fundamentally resolve this dilemma, structured context must not function as a passive memory notebook, but rather as an active decision-making state that directly steers forward conversational planning and downstream retrieval. Motivated by this insight, this paper formulates the multi-turn interaction as a Markov Decision Process and introduces a dual-node Monte Carlo Tree Search framework over structured dialogue states. Core idea: model conversational interactions as forward search over machine-readable structured states, decoupling and jointly optimizing preference elicitation via search over conversational action trees (ELNode) and preference exploitation via structured retrieval query refinement (EXNode) in a unified closed-loop lifecycle.
Method¶
Overall Architecture¶
DREAMS (Dual-node conversational RecommEndAtion system using Monte carlo tree Search) formulates the conversational recommendation lifecycle as a Markov Decision Process \(\langle \mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{P}, \gamma \rangle\), where the state space \(\mathcal{S}\) explicitly maintains JSON-structured preference trees encoding positive, negative, and ambiguous constraints, and the action space \(\mathcal{A}\) comprises attribute inquiries, failure reflections, item recommendations, and post-recommendation explanations. The interaction unfolds via two tightly coupled node types: during conversational turns, an Elicitation Node (ELNode) parses the user's latest utterance into structured updates and executes MCTS rollouts to anticipate the long-term utility of candidate conversational acts. Whenever the policy selects ItemRecommendation, an Exploitation Node (EXNode) is activated to transform the global cumulative preference state into noise-filtered, structured retrieval queries for item candidate scoring. User acceptance concludes the dialogue, whereas user rejection feeds back into the structured state, activating failure reflection for subsequent tree search rounds.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Multi-turn User Utterances & Context<br/>(Implicit/explicit preferences and feedback)"] --> B["Stage 1: ELNode State Parsing & Update<br/>Map free-form dialogue to JSON state"]
B --> C["Stage 2: MCTS Conversational Action Search<br/>UCT selection / LLM expansion / Rollout evaluation"]
C -->|Select inquiry/reflection action| D["Generate Natural Language Clarification<br/>(e.g., GenreInquiry / FailureReflection)"]
C -->|Action Transition: ItemRec| E["Stage 3: EXNode Query Refinement<br/>Eliminate conversational noise / Rewrite attribute constraints"]
E --> F["Stage 4: Hierarchical Verifiable Reward & Retrieval<br/>Attribute overlap matching + Candidate ranking"]
F --> G{"Does User Accept Recommendation?"}
G -->|Accept| H["Successful Recommendation Reached [END]"]
G -->|Reject| I["Write Back Feedback & Negative Preference<br/>Trigger failure reflection & initialize next search round"]
I --> B
Key Designs¶
1. ELNode Preference Tracking & Lookahead Action Search: Transforming Heuristics into Forward Strategic Planning
Targeting the failure of standard prompting to resolve ambiguous feedback and plan conversational trajectory, the ELNode incorporates an LLM semantic parser that translates free-form user utterances into explicit JSON key-value updates (e.g., mapping "not a big fan of Spike Lee" to {"director": "dislike Spike Lee"}). It maintains an evolving machine-readable state of positive, negative, missing, and corrected attributes. On top of this state, DREAMS executes Monte Carlo Tree Search, employing the UCB1 selection rule to balance action exploitation and exploration:
$\(a^* = \arg\max_{a' \in \mathcal{A}(s_i)} \left[ \frac{\mathcal{R}(s_i, a')}{\mathcal{N}(f(s_i, a'))} + c \sqrt{\frac{2 \ln \mathcal{N}(s_i)}{\mathcal{N}(f(s_i, a'))}} \right]\)$
During expansion, an LLM prior distribution prunes unpromising dialogue branches, followed by simulation rollouts guided by an online user simulator initialized from the current preference state. The final action is determined by integrating visit statistics with the LLM prior via \(\max_a [W_{\text{tree}} \frac{\mathcal{N}(f(s_0, a))}{\mathcal{N}(s_0)} + W_{\text{LLM}} \mathcal{M}(s_0, a)]\). This lookahead mechanism prevents premature guessing and prioritizes clarification actions that maximize long-term preference discovery.
2. EXNode Structured Query Refinement: Suppressing Contextual Noise for Grounded Retrieval
In standard conversational recommenders, passing raw dialogue transcripts into dense encoders severely degrades retrieval accuracy due to conversational noise and outdated negations. The Exploitation Node (EXNode) addresses this bottleneck. Unlike the ELNode, which tracks incremental turn updates \(s_t\), the EXNode aggregates cumulative multi-turn preferences into a comprehensive profile \(s_t^R\). It then instructs an LLM to generate targeted refinement actions \(a_i^R\)—such as pruning irrelevant chitchat, reordering salient attribute weights, and standardizing informal phrasing into canonical entity constraints. Each refined candidate query \(\text{EXN}^i \leftarrow a_i^R(\text{EXN}_0)\) is evaluated against the target profile via candidate retrieval scoring: $\(\mathcal{R}_R(\text{EXN}^i) = \text{score}(\text{retrieve}(\text{EXN}^i))\)$ The highest-scoring structured query is deployed for final candidate ranking, ensuring that the retrieval embedding space aligns strictly with true user constraints rather than noisy dialogue tokens.
3. Hierarchical Verifiable Reward Design: Combining Dense Process Signals with Objective Attribute Verification
To overcome the slow convergence and credit assignment challenges of sparse end-of-dialogue rewards, DREAMS designs a multi-faceted, verifiable reward function computed at each simulated transition: $\(r_t = \lambda_e r_{\text{explore}}^t + \lambda_r r_{\text{retrieve}}^t + \lambda_u r_{\text{attitude}}^t - \lambda_c r_{\text{cost}}^t\)$ Here, the exploration reward \(r_{\text{explore}}^t\) credits actions that clarify missing or ambiguous attributes in the preference state. Crucially, the retrieval reward \(r_{\text{retrieve}}^t\) computes the factual attribute overlap between the top-1 retrieved item \(A(\hat{y}_t^{(1)})\) and the simulator's ground-truth preference profile, providing an objective, externally checkable signal that eliminates subjectivity from LLM-as-a-judge scoring. The attitude reward \(r_{\text{attitude}}^t\) penalizes rejections and rewards acceptances, while \(r_{\text{cost}}^t\) penalizes unnecessarily prolonged dialogues. This dense supervision guides backpropagation toward policies that efficiently converge on correct recommendations.
4. Experience-Augmented Planning (DREAMS-EA): Bypassing Online Latency via Isomorphic Trajectory Retrieval
While tree search yields superior decision quality, multi-step online simulation introduces inference latency that can hinder real-time deployment. To overcome this limitation, DREAMS introduces an Experience-Augmented variant, DREAMS(EA). During offline interaction, successful and failed MCTS trajectories from 50 user profiles are harvested into an Experience Knowledge Base (EKB) formatted as tuples \(\langle \mathcal{D}, \mathcal{S}, a, r, q', \mathcal{R} \rangle\) (capturing context, structured state, action, rationale, refined query, and return). At inference time, the system computes semantic similarity between the current structured state \(\mathcal{S}\) and stored experience states, retrieving an isomorphic contrastive pair (one successful and one failed exemplar) to warm-start direct policy generation. By steering the LLM to follow successful patterns and avoid documented failure modes, DREAMS(EA) bypasses online tree search entirely, slashing per-turn inference latency from 23–34s down to 9s while maintaining high recommendation accuracy (Recall@1 = 0.467) with minimal memory footprint (~560MB).
A Worked Example¶
Consider an interaction on movie recommendation where the user query exhibits semantic ambiguity: "I really dig movies that are packed with excitement and thrilling actions, but I also love a good laugh... Got any suggestions?"
- Baseline Failure Spiral: Both ChatCRS and RA-CRS latch onto the superficial word "thrilling" and classify the genre as Thriller. Lacking lookahead planning, they immediately trigger ItemRecommendation and recommend dark comedy-thrillers such as Good for Nothing (2014) or Treehouse Hostage (1999). The user rejects these suggestions ("I don't like the theme of thrillers. I prefer daring adventure plots"), yet the baselines continue offering thriller-adjacent films, spiraling into repeated rejections.
- DREAMS Execution Pipeline:
1. The ELNode semantic parser extracts candidate preferences but identifies an ambiguity between Action and Thriller, flagging genre confidence as uncertain;
2. During MCTS expansion, the LLM prior favors immediate recommendation (ItemRec prior = 0.44 vs GenreInq = 0.35); however, tree rollouts assign a negative return to premature recommendation (-4.6) and a high return to clarifying the genre (+10.2);
3. Consequently, GenreInquiry secures the highest visit ratio (0.667) and final score (0.524), leading DREAMS to ask: "To clarify, when you mention thrilling actions, do you mean action-oriented films specifically, or are you referring more broadly to genres like thriller or crime?";
4. The user clarifies their preference: "Definitely leaning more toward action movies—intense fight scenes, high stakes";
5. The EXNode consolidates the preference state into {"genre": ["action", "adventure", "comedy"], "dislike": "thriller"}, generating a structured retrieval query that retrieves Men in Black (1997), which matches all attributes and is accepted immediately by the user.
Benchmark & Evaluation Protocol¶
Experiments are conducted on two widely acknowledged conversational recommendation benchmarks: ReDial (movie recommendation) and OpenDialKG (multi-domain: movies and books). DREAMS is benchmarked against eight representative baselines spanning pre-trained language models (BARCOR, UniCRS), free-form LLM-based CRSs (InterCRS, MACRS, ChatCRS, PC-CRS), semi-structured state tracking (RA-CRS), and tree-search methods (SAPIENT-LLM, T-EPL). In addition to standard recommendation metrics (Success Rate [SR] and Recall@K), the evaluation incorporates diagnostic error metrics: 1. Coarse-Grained Elicitation Error (CGE²): Quantifies high-level decision mismatches where the system asks questions when retrieval is already accurate, or recommends items when retrieval is inaccurate; 2. Fine-Grained Elicitation Error (FGE²): Measures the proportion of dialogue turns following a user rejection where the system ignores feedback and executes irrelevant inquiries or repeated premature recommendations; 3. Preference Exploitation Error (PE²): Evaluates the failure rate of item retrieval after the user simulator has fully and explicitly disclosed all key preferences.
Key Experimental Results¶
Main Results¶
Across all benchmark datasets and domains, DREAMS consistently achieves state-of-the-art performance in both recommendation accuracy and dialogue success rate. All LLM-based models utilize GPT-4o-mini as the backbone and text-embedding-ada-002 as the retrieval encoder.
| Model | ReDial R@1 ↑ | ReDial R@5 ↑ | ReDial SR ↑ | OpenDialKG (Movie) R@1 ↑ | OpenDialKG (Movie) SR ↑ | OpenDialKG (Book) R@1 ↑ | OpenDialKG (Book) SR ↑ |
|---|---|---|---|---|---|---|---|
| PLM-based | |||||||
| BARCOR | 0.193 | 0.467 | 0.107 | 0.094 | 0.211 | 0.106 | 0.219 |
| UniCRS | 0.147 | 0.373 | 0.133 | 0.233 | 0.250 | 0.225 | 0.231 |
| LLM-based | |||||||
| InterCRS | 0.213 | 0.370 | 0.313 | 0.439 | 0.494 | 0.356 | 0.394 |
| MACRS | 0.310 | 0.410 | 0.400 | 0.506 | 0.522 | 0.506 | 0.544 |
| ChatCRS | 0.367 | 0.473 | 0.440 | 0.539 | 0.550 | 0.494 | 0.531 |
| PC-CRS | 0.307 | 0.427 | 0.407 | 0.556 | 0.567 | 0.519 | 0.563 |
| RA-CRS | 0.273 | 0.340 | 0.333 | 0.422 | 0.433 | 0.494 | 0.519 |
| SAPIENT-LLM | 0.287 | 0.387 | 0.380 | 0.433 | 0.450 | 0.488 | 0.506 |
| T-EPL | 0.293 | 0.367 | 0.327 | 0.416 | 0.427 | 0.475 | 0.494 |
| DREAMS (Ours) | 0.507 | 0.633 | 0.560 | 0.600 | 0.639 | 0.550 | 0.594 |
Diagnostic elicitation and exploitation error metrics are detailed below, demonstrating significant reductions in systemic decision faults:
| Model | ReDial SR ↑ | ReDial FGE² ↓ | ReDial CGE² ↓ | ReDial PE² ↓ | OpenDialKG (M) SR ↑ | OpenDialKG (M) FGE² ↓ | OpenDialKG (M) CGE² ↓ | OpenDialKG (M) PE² ↓ |
|---|---|---|---|---|---|---|---|---|
| MACRS | 0.400 | 0.187 | 0.456 | 0.220 | 0.522 | 0.150 | 0.431 | 0.106 |
| ChatCRS | 0.440 | 0.120 | 0.561 | 0.200 | 0.550 | 0.133 | 0.291 | 0.117 |
| RA-CRS | 0.333 | 0.333 | 0.461 | 0.240 | 0.433 | 0.161 | 0.398 | 0.122 |
| SAPIENT-LLM | 0.380 | 0.307 | 0.443 | 0.233 | 0.450 | 0.150 | 0.348 | 0.139 |
| T-EPL | 0.327 | 0.313 | 0.469 | 0.253 | 0.427 | 0.144 | 0.332 | 0.133 |
| DREAMS | 0.560 | 0.100 | 0.289 | 0.160 | 0.639 | 0.117 | 0.304 | 0.078 |
Ablation Study¶
Ablation experiments isolate the contributions of structured preference representation, forward tree search, and query refinement.
| Configuration | ReDial R@1 ↑ | ReDial SR ↑ | ReDial FGE² ↓ | ReDial CGE² ↓ | ReDial PE² ↓ | OpenDialKG (M) R@1 ↑ | OpenDialKG (M) SR ↑ | OpenDialKG (M) PE² ↓ | Description |
|---|---|---|---|---|---|---|---|---|---|
| DREAMS (Full) | 0.507 | 0.560 | 0.100 | 0.289 | 0.160 | 0.600 | 0.639 | 0.078 | Full dual-node structured MCTS system |
| w/o EXNode | 0.407 | 0.487 | 0.133 | 0.311 | 0.193 | 0.517 | 0.572 | 0.117 | Retrieves directly from free-form context without query refinement |
| w/o ELNode | 0.393 | 0.427 | 0.173 | 0.417 | 0.173 | 0.500 | 0.550 | 0.094 | Replaces MCTS action search with direct heuristic LLM selection |
| w/o ELNode & Json | 0.287 | 0.347 | 0.340 | 0.539 | 0.233 | 0.450 | 0.478 | 0.111 | Degrades completely to ungrounded free-form dialogue |
| w/ Json Only | 0.327 | 0.360 | 0.200 | 0.455 | 0.240 | 0.439 | 0.472 | 0.128 | Keeps JSON states but selects actions/queries without tree search |
Key Findings¶
- Structured States and Forward Tree Search Are Mutually Indispensable: The ablation demonstrates that structured states without search (
w/ Json Only) yield only modest gains over raw text (SR increases from 0.347 to 0.360, while CGE² remains elevated at 0.455). Conversely, search without structured states (as in SAPIENT-LLM and T-EPL) struggles due to ungrounded exploration. Coupling structured states with MCTS enables DREAMS to reduce CGE² to 0.289 and FGE² to 0.100, showing that structured context must actively inform decision tree rollouts. - Long-Context Window Does Not Overcome Free-Form Context Noise: Evaluating on Gemini-2.5-flash with a 1M token context limit (Table 11) reveals that free-form InterCRS still suffers from high decision error (CGE² = 0.503, SR = 0.347), whereas DREAMS maintains superior performance (SR = 0.587, CGE² = 0.277). This empirically proves that conversational degradation stems from semantic noise and lack of state grounding rather than context window capacity.
- EXNode Solves Downstream Retrieval Degradation: Removing the EXNode triggers a steep 10.0% drop in ReDial Recall@1 (from 0.507 to 0.407) and increases PE² to 0.193. Cosine similarity analysis against ground-truth item descriptions confirms that EXNode query refinement consistently steers query embeddings toward ground-truth targets while standard LLM paraphrasing introduces high variance.
- Efficient Latency Scaling via Experience Augmentation: Parameter analysis indicates that setting \(n(\text{El})=5, k(\text{El})=3, n(\text{Ex})=3\) achieves peak performance. Leveraging these trajectories in DREAMS(EA) cuts inference time from 34s to 9s per turn while maintaining a competitive Recall@1 of 0.467, outperforming baselines like MACRS (18s / 0.289) and PC-CRS (13s / 0.378) in both speed and accuracy.
Highlights & Insights¶
- Dual-Node Decoupled Architecture: Separating the conversational interaction into distinct ELNodes (focusing on strategic action exploration) and EXNodes (focusing on structured query synthesis) resolves the historical tension between dialogue policy planning and retrieval optimization.
- Verifiable Process Rewards Overcome LLM Subjectivity: By formulating the simulation reward on objective attribute overlap between retrieved candidates and simulator ground truth, the framework provides dense, leak-free supervision without relying on noisy generative self-critique.
- Isomorphic Experience Knowledge Base for Practical Deployment: The DREAMS(EA) framework stores and matches structural state isomorphisms rather than raw text, providing contrastive guidance (successful vs. failed trajectories) that warm-starts policy generation and makes tree-search-level planning viable in latency-sensitive industrial applications.
Limitations & Future Work¶
- Author-Acknowledged Limitations: The empirical evaluation relies primarily on GPT-4o-mini and Gemini-2.5-flash due to computational budget constraints, leaving open the investigation of larger foundation backbones (e.g., Claude 3.5 Sonnet or full GPT-4o); furthermore, simulator-based benchmarks may inherit artifacts from predefined preference ontologies.
- Action Space Domain Dependency: The current inquiry action space relies on predefined schema facets (genres, stars, directors), requiring automated facet induction when expanding to unconstrained open-domain scenarios.
- Future Directions: The dual-node search paradigm holds significant promise for general-purpose task-oriented agents (e.g., travel booking or clinical diagnosis), where information gathering and tool-calling execution can be modeled respectively as exploratory and exploitative nodes.
Related Work & Insights¶
- vs. Free-Form Context CRSs (InterCRS, ChatCRS, PC-CRS): Conventional methods directly prompt LLMs with conversational history, causing severe context dilution and uncalibrated recommendations; DREAMS establishes an explicit JSON state with forward MCTS planning, yielding a +9.07% average improvement in success rate.
- vs. Static State Trackers (RA-CRS): RA-CRS summarizes history into JSON snapshots but treats them as turn-isolated static memory; DREAMS operationalizes structured states through tree search, increasing next-action prediction accuracy from 0.542 to 0.758.
- vs. Generic MCTS CRSs (SAPIENT, T-EPL): Earlier tree-based systems employ ungrounded free-form nodes restricted exclusively to the elicitation phase; DREAMS grounds all search operations in structured semantic states and bridges elicitation with exploitation in a unified closed-loop framework.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Formulates conversational recommendation as dual-node tree search over structured dialogue states, unifying preference elicitation and exploitation.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous evaluation across multiple benchmarks, interactive human studies (60 participants), diagnostic error metrics (CGE², FGE², PE²), and comprehensive ablation/efficiency analyses.
- Writing Quality: ⭐⭐⭐⭐⭐ Lucid mathematical formalization, compelling motivational narrative, and crystal-clear case study demonstrations.
- Value: ⭐⭐⭐⭐⭐ Establishes a foundational paradigm for structured context modeling and strategic dialogue planning in modern conversational systems.