Broaden your SCOPE! Efficient Conversation Planning for LLMs with Semantic Space
Conversation Planning;Tree search for LLM
Yes
No ethics review needed.
How does SCOPE handle the potential bias introduced by the semantic embedding model？
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.
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.
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.
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
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).
- 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.
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.
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.
Conversation planning typically uses many LLM queries for look-ahead simulation to select responses that maximize long-term rewards. By learning transition and reward models in text semantic space, we conversation plan without needing LLM queries.
@inproceedings{
anonymous2024broaden,
title={Broaden your {SCOPE}! Efficient Conversation Planning for {LLM}s with Semantic Space},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=3cgMU3TyyE},
note={under review}
}
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 gives the advantage of allowing the optimal LLM response to be selected 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Conversation Planning Tree search for LLM
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/62c1178f74628ea22d8144ccb4c32b62cad48b93.pdf
foundation or frontier models, including LLMs
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Broaden your SCOPE! Efficient Conversation Planning for LLMs with Semantic Space
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission