Broaden your SCOPE! Efficient Multi-turn Conversation Planning for LLMs with Semantic Space

Authors: Zhiliang Chen, Xinyuan Niu, Chuan-Sheng Foo, Bryan Kian Hsiang Low
Primary area: foundation or frontier models, including LLMs
Keywords: multi-turn conversation planning, multi-turn llm optimization, mcts, semantic space

Abstract:
Large language models (LLMs) are used in chatbots or AI assistants to hold conversations with a human user. In such applications, the quality (e.g., user engagement, safety) of a conversation is important and can only be exactly known at the end of the conversation. To maximize its expected quality, conversation planning reasons about the stochastic transitions within a conversation to select the optimal LLM response at each turn. Existing simulation-based conversation planning algorithms typically select the optimal response by simulating future conversations with a large number of LLM queries at every turn. However, this process is extremely time-consuming and hence impractical for real-time conversations. This paper presents a novel approach called Semantic space COnversation Planning with improved Efficiency (SCOPE) that exploits the dense semantic representation of conversations to perform conversation planning efficiently. In particular, SCOPE models the stochastic transitions in conversation semantics and their associated rewards to plan entirely within the semantic space. This allows us to select the optimal LLM response at every conversation turn without needing additional LLM queries for simulation. As a result, SCOPE can perform conversation planning 70 times faster than conventional simulation-based planning algorithms when applied to a wide variety of conversation starters and two reward functions seen in the real world, yet achieving a higher reward within a practical planning budget. Our code can be found at: https://github.com/chenzhiliang94/convo-plan-SCOPE.

Decision: accept (spotlight)
Reviewer scores: 8, 8, 6

Reviews and discussion:
<thread>
creation date:
1729570985717

thread_type:
official_review

<thread_object>
creator: reviewer_cm3a

<content>
summary:
This paper focuses on speeding up MCTS in semantic space to improve dialogue policy planning. The author proposes SCOPE, a method to convert dialogue into transition/reward functions in semantic space (i.e., embedding space), and then conduct MCTS to determine the optimal response. Specifically, SCOPE obtains the transition function by 1) convert dialogues into embeddings using LLaMA-2 Guard, and then 2) train a model to model state transition using an existing conversation dataset. Then, SCOPE obtains the reward function by similarly training a model to predict the reward associated with each state in the semantic space. Finally, the author evaluated SCOPE against methods such as rejection sampling (i.e., 0-step greedy) and MCTS, and show that SCOPE can achieve superior performance with significantly less compute.

strengths:
- Conducting MCTS in semantic space by modeling the transitions/reward functions in semantic space is novel. As the author mentioned, such an approach significantly reduces the search time from MCTS while retaining a high performance (if the transition/reward can be learned well)

- The authors supported many subtle claims with empirical evidences/theoretical analysis (in Appendix). For example, Appendix A.7 provides additional details to verify the effectively of using probabilistic models for stochastic transitions, and Appendix A.2 presents theoretical justifications for the optimal solution in semantic space, and more. This indicates that the proposed method/problem has been well thought and studied.

- The authors evaluated their approach against popular methods such as MCTS, and showed improvement in performance despite using much less test-time compute.

weaknesses:
1. While the authors argue that "our paper focuses on the training-free setting and explores inference time strategies" (L59), SCOPE is not training free, as it requires training the transition and reward model before test time. This makes direct comparison (e.g., performance v.s. speed) to prompt-based MCTS unfair, as the latter strictly uses no training.

2. This work trains a transition function to predict $T(s) \to (a',s')$ instead of $T(s, a') \to s'$, based on description in L287-293. This means that this transition function needs to *predict both the response that will be generated by the LLM and next the corresponding user response*. This seems unrealistic because 1) if it can accurately model $a'$ then it essentially becomes an LLM, and 2) the planning process becomes *policy agnostic* (also see Algorithm 1 line 7) - a sign indicating that SCOPE may not be robust against using different LLMs as policy models (unlike prompt based MCTS).

3. Since SCOPE requires a trained transition and reward function in latent space, it becomes questionable whether SCOPE can generalize when *evaluation dialogues become OOD compared to the ones used to train the transition/reward function*; or when different LLMs is used to propose candidates at test time.

4. Since SCOPE planning is conducted in latent semantic space, there is a lack of transparency/explanability in its decision making process. This is in contrast to approaches that plans in text space (e.g., prompt based MCTS). This could present difficulties to researchers or users to understand how or why certain actions were chosen.

questions:
Questions:

- In experiments you used $\lambda=0.1$ for UCT, which forces the tree search to focus on exploitation instead of exploration. This is rather an uncommon value. Is there a reason for this?
- Can you provide more details about the benchmarks you tested? Currently its only mentioned in L363-365 as "dialogue datasets consisting of open conversations and dialogue between LLM and humans". Are these generic dialogues from existing chat datasets or are these curated from certain dialogue planning benchmarks?

Comments and Typos:

- Planning in semantic/latent space (L108-111) has been explored in some prior work [1-2]. These should be mentioned in this paper as related work.
- In L259 and L346, it should be "conversation states s" instead of "conversation starter s"
- Currently Introduction and Background/Related work takes up more than 4 pages. This is too long, as it leaves little room for methods and experiments. I would suggest the authors to trim Section 1-3 as much as possible (e.g., details about MCTS can be moved to appendix).
- "Section 6.5 Conclusion" should be "Section 7 Conclusion".
- If I understood correctly, "0-step greedy" directly chooses the best response according to the reward model? If so, this should be named "rejection sampling" instead, which is a common approach used in many RL related work.


---

References

[1] Lubis, Nurul et al. “LAVA: Latent Action Spaces via Variational Auto-encoding for Dialogue Policy Optimization.” ArXiv abs/2011.09378 (2020): n. pag.

[2] Vlastelica, Marin et al. “Taming Continuous Posteriors for Latent Variational Dialogue Policies.” AAAI Conference on Artificial Intelligence (2022).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730260124889

thread_type:
official_review

<thread_object>
creator: reviewer_5qmx

<content>
summary:
The authors propose a method called SCOPE (Semantic space COnversation Planning with improved Efficiency) which focuses on making conversation planning in LLMs more efficient. There is a need to look ahead at every point in the conversation to see if choosing a particular response will lead to a better conversation in the long run; however, the authors mention that current methods that use vanilla MCTS are time-consuming because an LLM will need to be queried multiple times to get all possible scenarios. 

Therefore the authors propose a method that doesn't involve querying an LLM when determining future states but rather leverage the semantic space for more efficient searching. More specifically SCOPE involves 1) training a Transition model that samples a state where a state is a conversation context ending in a Human Turn and 2) training a reward model that predicts the reward at a certain state. The reward is the number of tokens in the user output and harmlessness which is predicted from Llama-Guard 2. To project the conversation and response into a semantic space the authors use the feature layer of Llama Guard 2 as the semantic embedding.

The authors then compare their SCOPE method against a variety of baselines which include: not doing any conversation planning, doing conversation planning for only one step, vanilla MCTS (which is time-consuming) and selecting a random response. They evaluate by measuring the cumulative reward and find that SCOPE outperforms all these methods and is much more efficient than vanilla MCTS. Both the training and testing were done on the Lmsys-chat-1m and Daily Dialog datasets.

They ran ablation studies to find what is the best type of model architecture to use for their Transition model and how many turns is good enough to plan ahead.

strengths:
1) The goal of this paper is well motivated. Working towards a more efficient conversation planning method can help with customer experience since latency will decrease and it seems the proposed method is novel. I think this will further encourage future work in this area.

2) The paper is well-written and easy to follow. I appreciate diagrams such as Figure 8 which helped visualize their overall Algorithm. Additionally the explanation of their method is also clear and easy to follow. In addition to giving good details on their experimentation the authors also released their code which will make it useful for the community to reproduce and build off of.

weaknesses:
EDIT AFTER AUTHOR RESPONSE: I am satisfied with both answers from the authors regarding the reward model and evaluation. I believe my score is already high so will be keeping it as 8.

My biggest concern is around the evaluation of this method along with the reward model. 

Regarding the reward model: I think that the harmlessness metric makes sense and the use of Llama-Guard2 is a good decision. However for engagement I don't think just measuring the token length of the user response is enough. Yes that is definitely a fine proxy to have but I don't think it is enough and I don't think "greater commercial benefits" is a good enough motivation. For one thing if this method was say used in spoken conversations then token length wouldn't be a good enough metric. One idea is to perhaps measure how often is the user asking questions to show that they are engaged in the conversation. 

Regarding evaluation: Overall the authors look at maximizing the cumulative reward to determine what is the best method in this case which is a good setup but I would think having some human evaluation could help solidify their arguments unless they disagree in which case I'm happy to hear why.

questions:
As mentioned above if the authors can address my concern regarding evaluation and the choice of reward functions.

Another question I have is do you think the transition model you trained on those datasets will generalize to other unseen domains? Has this been looked at?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619874810

thread_type:
official_review

<thread_object>
creator: reviewer_o97t

<content>
summary:
This paper introduces SCOPE, a novel approach for efficient conversation planning with LLMs. It leverages dense semantic representations to model stochastic transitions and rewards within conversations, enabling faster planning without additional LLM queries. SCOPE achieves higher cumulative rewards compared to conventional simulation-based planning algorithms, demonstrating its effectiveness in real-time conversations.

strengths:
The main innovations of this paper:
Introduces the concept of representing conversations in a dense semantic space, which captures the semantics of natural language conversations effectively. This representation allows for the modeling of stochastic transitions within a conversation and their associated rewards. Compare with the language or token space, this method helps to achieve a significant improvement in planning speed and improves the diversity of LLM samples.

weaknesses:
The paper relies on a specific dataset (1msys/1msys-chat-1m) for training the transition models. It would be beneficial to demonstrate the generalizability of SCOPE by testing it on additional datasets or in different conversational contexts.

questions:
How does SCOPE handle the potential bias introduced by the semantic embedding model？
</content>
</thread_object>

</thread>
<thread>
creation date:
1733114427731

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to thank the reviewers for the reviews, positive comments and scores, specifically:
- SCOPE's novel use of dense semantic space to model transition and rewards for conversation planning in a light-weight fashion (all reviewers).
- SCOPE's ability to improve planning speed (more than 70x in our paper) in conversations without relying on expensive LLM queries (all reviewers).
- Our practical problem setting of conversation planning in areas such as customer experience (reviewer `5qmX`).
- Our paper's well-written presentation and figures (reviewer `5qmX`).
- Our paper's code reproducibility and well thought out empirical evidence/theoretical analysis (reviewers `5qmX`, `Cm3A`).

We would like to summarize our main responses and discussions during the rebuttal period.

- We clarified with specific empirical results that our approach is able to generalize to conversation starters that are not present in the transition model training data (all reviewers)
- We highlighted the validity of our reward function choices used in the paper and discussed evaluation metric alternatives that could be used in real-world settings (reviewer `5qmX`).
- We had a fruitful discussion about the merits of SCOPE as compared to other approaches such as prompt-based MCTS ("on-policy"). We noted that without real-time requirements or with significant runtime compute improvements, it's possible that other on-policy approaches in the future can potentially trade off time efficiency for better performance. Currently, our paper showed that SCOPE empirically achieves better performance with smaller runtime than other existing approaches, including on-policy ones like prompt-based MCTS. We also noted possible extension of SCOPE (e.g., fitting the transition model with conversation data produced by the specific LLM used during deployment) to address the "model-agnostic" point that reviewer `Cm3A` raised.
- We have incorporated writing suggestions and feedback from the reviewers in our revised paper to improve its presentation (changes in _blue_).

We appreciate the reviewers' time with us and sincerely hope SCOPE serves as a competitive baseline and foundation for future works on other possible conversation planning approaches in terms of performance-efficiency trade-off.

Best regards,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors propose a novel approach to conversation planning, called SCOPE, that addresses the time-consuming nature of existing simulation-based methods. SCOPE models stochastic transitions and rewards within the semantic space of conversations, enabling efficient selection of optimal LLM responses without requiring additional LLM queries for simulation. The reviewers appreciate the novelty of the approach, the evaluation and empirical results, and the overall clarity of presentation. However, they also raise some concerns, such as reliance on specific datasets (and how to generalize), limitations of the reward model, the "training-free" claim might not hold, and lack of explainability in SCOPE's decision making process. The authors provide detailed responses to all concerns and questions.