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

Part 2/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. [...] the planning process becomes policy agnostic

To clarify, the transition model we used in our experiments is trained from lmsys data, which comes mostly from conversations between a vicuna-based LLM and a human [3]. On the other hand, during our evaluation, we used Llama-3 as our LLM to generate LLM responses. Hence, even if a different LLM is used during test time, our method generalizes well and performs better than other baselines.

In addition, the dialogues we used for evaluation contain a mixture of conversation starters from DailyDialog and lmsys. DailyDialog data is not used to train our transition models. To make our results clearer, we took the evaluation starters which came from the Daily Dialogue dataset and show SCOPE's isolated performance on them. As we see from the table below, SCOPE outperforms other baselines even though the transition model is trained on a different conversation dataset (these results are already part of our paper's empirical results, just that we isolated and show them explicitly here). Hence, SCOPE still performs well for conversations not explicitly used to train the transition model.

Length (Higher is better; how much higher than random):

Harmful (Higher is better; how much higher than random):

We hypothesize that SCOPE generalizes well because even though different humans and LLMs converse differently, the stochastic transition of conversation semantics is approximately similar regardless. These are very interesting discussion points, and we would like to incorporate them in the revised paper, thank you.

---

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.

Thank you for the comment. While SCOPE achieves higher conversation rewards by planning in semantic space, we agree planning this way makes it difficult to interpret the decision process. We believe this is not an easy problem and should be left as a future research direction. One practical approach would be to use SCOPE for planning and when the need for interpretation arises, use prompt-based MCTS (with larger time budgets) to verify why a certain action is picked. Alternatively, we could use the encoder from an encoder-decoder model as the semantic embedding model, and using the decoder to interpret predicted states. We will mention this in our revised paper.

---

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?

We used $\lambda=0.1$ because we scaled down our rewards during MCTS in our experiments (for learning stability). As a result, the predictions for $Q_k(s,a)$ in Equation 3 are relatively small compared to the second term in the equation, and $\lambda=0.1$ was chosen to balance the 2 terms. Hence, it was sufficient enough to promote exploration as well. We will improve the writing by mentioning this in the appendix.

---

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?

Thank you for the question. We used actual conversation starters from the DailyDialog and lmsys dataset (around half of evaluation data is taken from each dataset, total of 100 starters for each evaluation task). We take the first turn statement for each conversation in those datasets and treat it as the conversation starter. The reason why we used lmsys is because it actually contains conversations between humans and LLMs, and occasionally some harmful topics. DailyDialog conversation is similar to real-world conversations, which we think future LLMs serving as chatbots or companions might encounter. We will improve the clarity of our experimental setup in the revised paper.

Part 3/3

Other Comments

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.

Thank you for pointing this out, we will cite [1] and [2] in our revised paper's related work for planning in semantic space. The key difference is that prior works attempt to learn a latent space policy by fine-tuning the language model. On the contrary, our method is more lightweight because it merely approximates the transition of conversation semantics, before using it to infer which LLM response leads to higher reward during inference time, without needing any LLM training.

---

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).

Thank you for the suggestion, we will try our best to trim the section. We felt that the details of MCTS is important in this paper (as opposed of just moving them entirely to appendix) because 1) it serves as a backbone to our algorithm and 2) after we project the conversations into semantic space, we want to explain precisely which part of MCTS stays the same and which part is now different.

---

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.

We chose the method name as 0-step greedy to mark out the clear distinction between greedy and non-myopic approaches. However, we are aware that some RL related work might have used rejection sampling to denote such methods. We will make a note in the revised paper that some literature might use a different name for such methods, to make it clearer for readers from different backgrounds.

---

In L259 and L346, it should be "conversation states s" instead of "conversation starter s"

"Section 6.5 Conclusion" should be "Section 7 Conclusion".

Thank you for the comments on our paper's writing. We will incorporate the reviewer's suggestion on related works and improve the writing in our revised paper.

---

Once again, we sincerely hope that our additional experimental results and clarifications have addressed your questions satisfactorily and improved your opinion on our work. If you are satisfied with the discussion, we will incorporate our responses and clarifications into the revised paper.

[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).

[3] Zheng et al. (2023) LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset

Part 1/3

We would like to thank the reviewer for the comprehensive review and compliments of our method's novelty and motivation.

The authors supported many subtle claims with empirical evidences/theoretical analysis (in Appendix). For example, [...] This indicates that the proposed method/problem has been well thought and studied.

First of all, we would like to thank the reviewer for these praises, it means a lot to us as researchers. We will provide additional clarifications to the reviewer's questions in our responses below.

---

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.

Thank you for the comment. In the context where that sentence was written, we were qualitatively comparing SCOPE with methods such as RLHF, which require us to fine-tune an LLM. That is why we claimed it was "training-free" w.r.t. LLM training. We will improve the writing to make the distinction clear that our method still needs some degree of training (but not on the LLM).

Even though our method needs to train a reward/transition model, we show in our paper that these models are relatively lightweight and can be trained beforehand (we only took an hour to train the transition model, and inference time is negligible) and kept fixed during inference time. In addition, for metrics such as harmfulness by the Llama-guard model, the mapping between semantic space and rewards is taken directly from the pre-trained model's weights and so we do not need to train a separate reward model. Hence, we believe it is still fair to compare the performance/speed of our method with vanilla MCTS. Our aim is to show that we can use a lightweight transition and reward model (both of which are fast to train) with almost no inference overhead to achieve faster and better conversation planning in real time. We will improve the writing of our revised paper by incorporating these clarifications.

---

This work trains a transition function to predict $T(s) \rightarrow (a',s')$ instead of $T(s,a') \rightarrow 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 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).

Thank you for the question. I think our usage of $T(\tilde{s},\tilde{a},\tilde{s}')$ gave the readers an impression that we are predicting the actions and states together. We would like to clarify that L287-293 actually states that the semantic transition function predicts $\tilde{s} \rightarrow \tilde{s}'$ (both $\tilde{s}$ and $\tilde{s}'$ are in semantic space) without explicitly predicting the LLM actions. Rather, the "action" for each transition is implicitly recovered as the directional vector $\tilde{a}'=\tilde{s}'-\tilde{s}$ (mentioned in Line 268). In our paper, we don't view or claim this "action"/vector as predicting an LLM response. Rather, we just use these "actions" as part of the MCTS process in the semantic space (e.g., in Algorithm 1 line 7, where we perform action selection and expansion in semantic space). The purpose of the semantic transition model is to predict the approximate transition of conversation semantics (we show that these predictions are reasonable in Sec. A.7) at each step, and does not represent LLM response prediction. Hopefully, this provides some clarification to the author's question.

I would like to follow up on the following question, which is my main technical concern about this work.

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 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).

Thank you for your response. My point here is that 1) a dialogue state $s$ essentially means a sequence of (user text, LLM text, user text, LLM text, ...), and that 2) going from a a dialogue state $s$ to the next one $s'$ only make sense if you have access to the next LLM text and a (simulated) user text.

You mentioned the semantic transition function directly predicts $s \to s'$. To my point above, I believe this already means that it has to model the next LLM text and user text (semantically). Even though "In our paper, we don't view or claim this "action"/vector as predicting an LLM response", I believe modeling $s \to s'$ is implicitly doing this. Otherwise how can you model transitioning from a dialogue state to the next one?

Please let me know if I misunderstood anything.

Thank you for the clarification. Before proceeding with my concern, I want to clarify my stance. I provided an overall positive score for this work, since I believe performing MCTS in a semantic/hidden space can speed up its inference time and is of practical value. However, as there is often no free lunch, the proposed method has limitations, i.e., requires transition model to be also in the semantic space without additional query to the language model for next actions (hence my comment on off-policy and model agnostic).

I feel like the authors are trying to address the "model agnostic" example I provided, but I note that I only mentioned it as an example to clarify my concern. I agree with the "fix" the author mentioned can be done to avoid that particular case, but I believe this misses my main point. I re-emphasize them below.

---

I am quite familiar with MCTS, but maybe I misunderstood your Algorithm 1. Given an initial dialogue state (e.g., a user query only), you have state $s_{init}$ as mentioned in Algo 1 Line 1-3. Then, in your first iteration of node expansion (Line 7), you need to call your transition model $\tilde{T}$ to obtain a new state. Since in this work you consider $\tilde{T}(s) \to s'$, Line 7 would result in new nodes/next state being identical regardless of what your policy model is?

• "We'd like to first clarify our algorithm: in SCOPE, our transition model does not predict $\tilde{s}$ to $\tilde{s}'$ directly in one single step."

  
  I note that the essence of my concern is that the only physical input your $\tilde{T}$ relies on is only a state, and its final output is the next state. This means future simulation is off-policy and model agnostic. It does not matter how you predict the next state, but rather there is an information bottleneck where your transition model does not query the language model policy for future actions and only relies on current states (i.e., dialogue history). This is in contrast to the other MCTS methods I mentioned that plans in text space, where to model future states they also query the language policy for its actual future actions to model transitions.

• "we are merely trying to make a clarification regarding the earlier question on whether simulation results are identical with different LLMs"

  
  The proposed algorithm proposed conducts simulation without relying on querying LLM for future responses, and practically the only place it queries the LLM is in the beginning (L2 in Algo 1). In general, I believe for your statement to strictly hold true there are two assumptions. 1) Different LLMs is guaranteed to provide distinct responses in L2 in Algo 1, and that 2) even when you received slightly different responses, they have to be different enough in semantic space such that all of your subsequent simulation reaches different outcomes (that are hopefully faithful to the actual LLM's behavior). There is also a concern whether or not your trained transition model can really differentiate semantic transitions for different policies when the only place the LLM is actually used is L2, but I believe this is an empirical question and is less of a concern given the generally positive results for the proposed method.

  
  My emphasis here is that these are not concerns for on-policy MCTS that queries the LLM during simulation, and are additional requirements for the proposed method to work well fundamentally due to the information bottleneck I mentioned in my previous point.

Part 1/2

We would like to thank the reviewer for the comprehensive review and compliments for our method's motivation, presentation and reproducibility. We would like to present our response to the reviewer's questions below.

---

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 [...] One idea is to perhaps measure how often is the user asking questions to show that they are engaged in the conversation.

Thank you for the question. We would like to emphasize that our method, SCOPE, is reward agnostic and one can use any reward function in SCOPE to plan. We agree with the reviewer that there might be other conversation engagement metrics that works better as the reward function. However, the actual choice of reward function is not the focus of our work - our main contribution (like what the reviewer has pointed out) is an efficient way to do conversation planning to maximize a reward function in the conversation MDP setting and our evaluation is done on two reward functions that, as the reviewer pointed out, serves as a good proxy for certain real-world applications (below, we provided more experimental results on another engagement evaluation metric). Hence, the best reward function depends heavily on the problem setting and the LLM owner's preference. We hope our paper can inspire people to try using SCOPE with other reward functions. We will re-emphasize this point in our revised paper.

---

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.

Thank you for the suggestion. We agree that human evaluation is the gold standard to evaluate conversations. For example, LLM owners can deploy SCOPE and use human annotators to rate whether more engaging conversations are produced. Unfortunately at this point of time, we do not have the time budget to conduct full-fledged human evaluation. Despite so, we believe cumulative rewards, as the reviewer put it, serve as a good proxy for an evaluation metric. To make our evaluation stronger, we adopted the reviewer's advice of measuring "how often the user is asking questions to show that they are engaged in the conversation" to check if SCOPE indeed produces more engaging conversations (we still use cumulative rewards for planning, but during evaluation, we check if the user is asking questions in the resulting conversation). The results show that in conversations produced by SCOPE, the user on average asks more questions, signaling that they are more engaged with the conversation.

We will include the additional experiments and add some discussion regarding human evaluation in our revised paper.

Part 2/2

do you think the transition model you trained on those datasets will generalize to other unseen domains? Has this been looked at?

We trained our transition model with the lmsys dataset but in our experiments, we also evaluated SCOPE on conversation starters from the Daily Dialog dataset [1] (see line 1057 for detailed experimental setup) which contains different dialogues as compared to lmsys dataset. Furthermore, the lmsys dataset contains mostly dialogues from the vicuna model, while our experiments were evaluated on the Llama-3 model. Therefore, it can be seen that SCOPE indeed generalizes to conversation contexts outside of the data used to train our transition model, achieving higher cumulative rewards.

To make our results clearer, we took the evaluation starters which came from the Daily Dialogue dataset and show SCOPE's isolated performance on them. As we see from the table below, SCOPE outperforms other baselines even though the transition model is trained on a different conversation dataset (this result is already part of the empirical results in Fig. 3 of our paper, just that we show it in isolation here).

Length (how much longer was human responses in the conversation as compared to random)

Harmful (how much less harmful (Llama-guard) was the conversation as compared to random)

In real-world settings, an LLM owner can also use a user's data (if they permit) to fine-tune the transition models to match the user's demographic and speaking pattern, possibly improving SCOPE's effectiveness even further. This will be an interesting future research direction, which we will mention in our revised paper.

---

We sincerely hope that our additional experimental results and clarifications have addressed your questions satisfactorily and can improve your opinion of our work. If you are satisfied with the discussion, we would incorporate our responses into the revised paper.

[1] Li, et al. (2017). DailyDialog: A Manually Labelled Multi-turn Dialogue Dataset.

We would like to thank the reviewer for the comprehensive review and compliments for our method's innovation and contribution in making conversation planning faster.

---

To address the reviewer's comments, we have provided additional clarifications. We hope you find them enlightening and useful.

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.

Even though we trained our transition model with the lmsys dataset, in our experiments, the set of conversation starters that SCOPE is evaluated on contains starters from the Daily Dialogue dataset [1] (line 1057 for detailed experimental setup), which has different conversation starters from the lmsys dataset. Therefore, it can be seen that SCOPE indeed generalizes to conversations outside of the data used to train our transition model, achieving higher cumulative rewards.

To make our results clearer, we took the evaluation starters which came from the Daily Dialogue dataset and show SCOPE's isolated performance on them. As we see from the table below, SCOPE outperforms other baselines even though the transition model is trained on a different conversation dataset (this result is already part of our paper's empirical results, just that we show it in isolation here).

Length (Higher is better; how much higher than random):

Harmless score (higher is better; how much higher than random):

In real-world settings, an LLM owner can also use a user's data (if they permit) to fine-tune the transition models to match the user's demographic and speaking pattern, possibly improving SCOPE's effectiveness even further. This will be an interesting future research direction, which we will mention in our revised paper.

---

How does SCOPE handle the potential bias introduced by the semantic embedding model？

Thanks for the interesting question. As we pointed out in Section A.8 (How does transition and reward model performance affect SCOPE?) and our experiments, even when our semantic embedding or transition model has some inaccuracies, our empirical results have shown that SCOPE still achieves higher cumulative rewards than other methods. There could be a few explanation for this. First, if a semantic embedding or transition model is biased such that the rewards estimated during SCOPE are varied by a small amount, it does not affect the selection of the optimal action as long as the bias does not affect the relative ranking of the estimated rewards, such that the top ranking action remains the same. Second, even if there are errors in the models, because SCOPE is able to perform so many more rounds of MCTS rollouts (92 times more than vanilla MCTS, according to section A.9) within a short amount of time, it can still estimate the rewards associated with each possible LLM response more accurately than conventional MCTS (which uses LLM simulation) that has large sampling error due to insufficient number of rollouts within a tight planning budget.

Once again, thank you for the positive feedback and comments. We sincerely hope that our clarifications have addressed your questions satisfactorily and can improve your opinion of our work. If you are satisfied with the discussion, we would incorporate our responses above to improve our paper's writing and clarity.

[1] Li, et al. (2017). DailyDialog: A Manually Labelled Multi-turn Dialogue Dataset.