# Feedback-Aware Monte Carlo Tree Search for Efficient Information Seeking in Goal-Oriented Conversations

arXiv: https://arxiv.org/abs/2501.15056 · HTML: https://mlsanity.com/paper/2501.15056/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 21 references that are in the map.
- First posted on arXiv 25 Jan 2025.

## Builds on (most cited first, 14 of 14)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents](https://mlsanity.com/paper/2408.07199/) (2024)
- [MediQ: Question-Asking LLMs and a Benchmark for Reliable Interactive Clinical Reasoning](https://mlsanity.com/paper/2406.00922/) (2024)
- [End-to-End Knowledge-Routed Relational Dialogue System for Automatic Diagnosis](https://mlsanity.com/paper/1901.10623/) (2019)
- [Prompt-Based Monte-Carlo Tree Search for Goal-Oriented Dialogue Policy Planning](https://mlsanity.com/paper/2305.13660/) (2023)
- [Learning to Search with MCTSnets](https://mlsanity.com/paper/1802.04697/) (2018)
- [Adaptive Information Seeking for Open-Domain Question Answering](https://mlsanity.com/paper/2109.06747/) (2021)
- [End-to-End Learning of Flowchart Grounded Task-Oriented Dialogs](https://mlsanity.com/paper/2109.07263/) (2021)
- [RoT: Enhancing Large Language Models with Reflection on Search Trees](https://mlsanity.com/paper/2404.05449/) (2024)
- [Monte-Carlo Robot Path Planning](https://mlsanity.com/paper/2208.02673/) (2022)

## Built on by (most cited first, 6 of 6)

- [AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization](https://mlsanity.com/paper/2602.20133/) (2026)
- [EvoX: Meta-Evolution for Automated Discovery](https://mlsanity.com/paper/2602.23413/) (2026)
- [CaRT: Teaching LLM Agents to Know When They Know Enough](https://mlsanity.com/paper/2510.08517/) (2025)
- [DDO: Dual-Decision Optimization for LLM-Based Medical Consultation via Multi-Agent Collaboration](https://mlsanity.com/paper/2505.18630/) (2025)
- [MIND: Unified Inquiry and Diagnosis RL with Criteria Grounded Clinical Supports for Psychiatric Consultation](https://mlsanity.com/paper/2603.03677/) (2026)
- [CA-BED: Conversation-Aware Bayesian Experimental Design](https://mlsanity.com/paper/2606.01182/) (2026)

## Abstract (arXiv)

Effective decision-making and problem-solving in conversational systems require the ability to identify and acquire missing information through targeted questioning. A key challenge lies in efficiently narrowing down a large space of possible outcomes by posing questions that minimize uncertainty. To address this, we introduce a novel framework that leverages Large Language Models (LLMs) to generate information-seeking questions, with Monte Carlo Tree Search (MCTS) to strategically select questions that maximize information gain, as a part of inference-time planning. Our primary contribution includes a hierarchical feedback mechanism that exploits past interaction patterns to guide future strategy. Specifically, each new problem is mapped to a cluster based on semantic similarity, and our UCT (Upper Confidence bound for Trees) formulation employs a cluster-specific bonus reward to prioritize successful question trajectories that have proven effective for similar problems in the past. Extensive empirical evaluation across medical diagnosis and technical troubleshooting domains shows that our method achieves an average of 12% improvement in success rates and about 10x reduction in the number of LLM calls made for planning per conversation, compared to the state of the art. An additional 8% gain in success rate is observed on average when we start with a constrained set of possibilities. Our results underscore the efficacy of feedback-aware MCTS in enhancing information-seeking in goal-oriented dialogues.