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
Venue: ICLR 2025 Spotlight (2025)
Keywords: Multi-turn Conversation Planning
Multi-turn LLM Optimization
MCTS
Semantic Space
Primary area: foundation or frontier models, including LLMs
TL;DR: 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.

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.

Published as a conference paper at ICLR 2025
BROADEN YOUR SCOPE! EFFICIENT MULTI-TURN CONVERSATION PLANNING FOR LLMS USING SEMANTIC SPACE
Zhiliang 122, Xinyuan Niu Chuan-Sheng Foo & Bryan Kian Hsiang Low
1 DDpartment of Computer Science, National University of Singapore
2 Instiiute for Infocomm Research (I2R), A Singapore
*Centre for Frontier AI Research (CFAR), A$STAR, Singapore achenzhiliame xinyuan @u. nus edu foo _to_cchuan___ @araannsshgg_aae i 2r a-star.......r............... www.sttrrrduu.e...
lowkh@ comp. nus. edu.sq
ABSTRACT
Large language models (LLMs) are used in chatbots or Al assistants to hold con- versations with a human user. such applications, the quality (e.g., user en- gagement, safety) of conversation is important and can only be exactly known the end of the conversation. To maximize its expected quality, conversa- tion planning reasons about the stochastic transitions within conversation to select the optimal LLM response each turn. Existing simulation-bar based con- versation planning algorithms typically select the optimal response by simulat- ing future conversations with a large number of L.M 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 plan- ning efficiently. In particular, SCOPE models the stochastic transitions in con- versation semantics and their associated rewards to plan entirely within the se- mantic space. By doing so, SCOPE selects the optimal LLM response every conversation turn without needing additional LLM queries for simulation. As a result, SCOPE can perform conversation planning 70 times faster than conven- tional simulation-basee planning algorithms when applied to wide variety of conversation starters and two reward functions seen in the real world, yet achiev- ing higher reward within practical planning budget. Our code can be found at: com/
INTRODUCTION
The rise of large language models (LLMs) has introduced numerous conversational tools in the market, such as Replika (bttps://zepliee conversational tools become widespread, there are significant commercial and regulatory interests in ensuring that they produce high quality conversations with the human users. For example, chatbot is commercially motivated to select responses at every conversation turn to produce longer and more engaging conversation with human user. In this case, the quality of a conversation can only be exactly known at the end of the conversation by accumulating the rewards (according to some metric such conversation engagement, safety) over multiple turns. To produce an optimal conversation where the cumulative reward across multiple turns is maximized, we need to perform conversation planning that reasons about the stochastic transitions in conversation strategically select an optimal LLM response at each conversation turn.
com) and chatbots (Dam et al.) (022)). As these
Several recent works are myopic in conversational planning because they merely select the LLM sponse that seems immediately "good" at each conversation turn. For example, one might be tempted use predefined reward function select the LLM response with the highest immediate reward
"Equal contribution.

---

Published as a conference paper at ICLR 2025
Yang al. 2023 at each turn. However, myopic approaches do not consider how the selected LLM response influences the conversation (and rewards) later on. This implies a response that seems good at first might not lead to better conversation rewards. In Appendix A..I] we give some illustrative examples where I.L. responses with similar instantaneous rewards even- tually lead to conversations of differing quality in metrics such conversation harmfulness. Hence, without explicitly reasoning about how a selected LLM response influences the conversation later, myopic approaches are suboptimal in maximizing the quality of the overall conversation.
(Kumar al. 2024
Alternatively, an LLM can be fine-tuned (Ouyang et al. 2022 Rafailov et al. 2023) to produce response that implicitly maximizes cumulative reward metric across multiple conversation turns. While non mymmmii if done correctly, these approaches are resource-intensive (Zhang et al. (024), re- quiring manual preference labels and repeated model fine-tuning. Therefore, fine-tuning approaches are impractical for an LLM owner deploying LLMs for different use cases that require different reward metrics. On the other hand, our paper focuses on the training-free setting (no fine-tuning of
LLMs) and explores inference time strategies (Lin al. 2024 Zhou et al. 2024b Wu et al. 2024 Xu et al.
2024) to select LLM responses in a conversation.
More recently, some works have also explored using LLMs and simulation-based search algorithms (Yu et al. 2023 Koh et al. 2024 Hao et al., 2023 Kim et al. 2024) to plan LLM--reatee prob- lems such goal-oriented dialogues (Yu et al. (202)). language games (Jang et al. 202T and more.
The popularity of these algorithms is driven mostly by the ubiquitous effectiveness of LLMs, using LLMs simulate conversation
(Liu et al. (023) to find out which responses lead higher mulative rewards in the simulated conversation. However, these simulation-based algorithms suffer from high planning costs (Koh al. 2024 Zhao al. 2023), requiring hundreds or even close to thousands of seconds to perform sufficient look-ahead simulation during runtime (details covered in Section 3.2 Such large planning budget luxury unavailable in
conversations, where human user expects the LLM to respond almost immediately. Thus, given practical planning budget, these simulation-base -based search algorithms do not achieve sufficient simulation scope to select optimal L.M responses. Furthermore, these L.M queries could also incur excessive monetary costs if they use API calls from external LLM providers. Therefore, conventional simulation- based algorithms impractical in our problem setting due to the large planning costs involved. In our experiments (Section 6.3). we show that such algorithms indeed perform poorly in conversation planning under practical planning budget.
Learning phase
Runtime (A Igorithm 1)
"Can you 1 tell about country XXX
Human
(a) Leam transition model in semantic space (Sec, 4.2).
(b) Learn reward model R in semantic space (Sec. 4.3).
LLM
Conversation
Semantic projection
Conversation
Conversation
Converation
Shmman
Use 7. R to search for best response in semantic space.
Conversation
Figure 1: Overview of our approach, SCOPE, for conversation planning. During learning phase (left), we exploit dense semantic representation of conversations to learn lightweight transition and reward model in semantic space (Notations and details covered in Sections 4.2 and 4.3). During runtime (right), SCOPE uses these learnt models to perform MCTS at a broader scope in semantic space without needing additional LLM queries for simulation (Algorithm D. allowing us to select an optimal LLM response that maximizes the cumulative reward a conversation.
This paper presents a novel approach called Semantic Space COnversation Planning with improved Efficiency (SCOPE) which exploits the dense semantic representation of conversations to perform conversation planning in semantic space (Figure [I] Such representations have been shown to capture the semantics of natural language conversations effectively (Devlin et al., 2019)) Chen et al.] 2020). During the learning phase, SCOPE learns the stochastic transitions in conversation and their
2

---

Published as a conference paper at ICLR 2025
associated rewards using a lightweight transition and reward model in semantic space. During time, SCOPE uses the learnt models to perform Monte Carlo tree search (MCTS) and simulation in semantic space, selecting an LLM response that leads to high quality conversations without using costly LLM queries. This results in a non-myopic approach that is effective even under realistic planning budgets. As such, our work presents paradigm shift, similar that found in Kamb- hampati et al. (2024): instead of relying on an LLM fully for simulation in conversation planning, our approach only uses an LLM propose candidate responses, before using SCOPE to plan in semantic space without needing costly LLM queries. Concretely, our contributions are:
We transform the multi-turn conversation planning problem, originally viewed Markov de- cision process (MDP), into its semantic form representation (Section 4.1). The semantic form preserves the optimal action (L.LM response) selected at every conversation turn in a real-time conversation.
We introduce a novel approach, SCOPE, that solves this transformed MDP by exploiting dense conversation semantic representations to learn lightweight transition and reward model over conversation semantics. By modeling the stochastic transitions within conversation and their associated rewards in semantic space, SCOPE performs MCTS entirely in semantic space with- out needing additional LLM queries to search for optimal LLM responses at every conversation turn. By doing so, SCOPE plans 70 times faster than conventional simulation-basee planning algorithms. allowing it to select optimal LLM responses under practical planning budget.
We use SCOPE to select LLM responses in a wide range of real-world multi-turn conversations and show that learning the transition and reward models semantic space allows SCOPE to achieve higher cumulative rewards than conventional non-myopic and myopic planning algo- rithms under practical planning budget and two realistic reward functions.
CONVERSATION PLANNING FOR LLMS
2.1
PROBLEM SETTING
Human: Can you tell me a
Stochastic transition
fact about Country XXX?
Our work focuses on real-time, multi-turn conversa- tions between the LLM and a human user. Briefly, a conversation consists of alternating responses given by each party at every conversation turn. Given a reward function which assigns numerical reward each conversation turn (dependent on the response given by the LLM and/or human user), conversation planning aims to select the optimal LLM response out of a can- didate pool of responses at every conversation turn, maximizing expected cumulative reward over multiple turns. With an appropriately chosen reward function (some examples given in Section 6.1). the cumulative reward indicates the overall quality of the conversation (e.g., engagement, safety). Con- versation planning is challenging because (a) we need to account for the stochastic response of the human user (which we cannot directly control) at every conversation turn and (b) an LLM response selected at the current turn influences later conversations, affecting future rewards obtained.
LLM: The world was held twice in Country XXx. a
s
Human: That's cool! didn't know that! Can you tell me more?
S'
Figure 2: Example of stochastic transi- tion from s to s' after taking action a in MDP for conversation planning.
Inspired by similar challenges found in the broad class of sequential decision making problems (Bellman 1957) and dialogue planning (Yu et al. 2023) containing stochastic environments and se- quential action selection, formulate conversation planning as Markov decision process (MDP) (Howard 2012) defined by A, I. R) shown in Figure where
S is set of states. Each state S is the conversation context comprising all responses given chronologically from prior conversation turns and ending in a human response.
A is a set of actions. Each action a e is an LLM response shown to the human user at a conversation turn. Similar prior works, a candidate set of LLM responses is generated each turn in which a is selected. After selecting an LLM response (i.e., taking action a), the human user responds, transitioning the conversation to a new state s' (see Figure 2).
T: S x A x S + [o. 1] is transition function specifying the probability of transitioning from a conversation state E S to the next state s' E after executing action a (i.c., selecting a particular L.MM response to show the human user) T captures how human user stochastically
3

---

Published as a conference paper at ICLR 2025
responds at every conversation turn. In our paper, we concerndd about modeling simulator to sample transitions from T and do not necessarily need to calculate the transition probability. R(s, a, 8') is an instantaneous reward function associated with the state transition every con- versation turn. This reward can be dependent both LLM and human response (i.e., dependent on s, a and s'), and is chosen by the LLM owner beforchand.
Given this MDP, our goal is to, at each conversation state select an LLM response o which max- imizes the expected cumulative reward (w..t. the stochastic transition function) over a conversation horizon (c.g., 5 conversation turns):
d² arg A EvEST(s, a, 8 (R)(R(ss, a,s +)V(s))
(I)
where is the discount factor (Amit et al. 2020) and V(s'), the value of state s', is recursively defined as
V(s') ma Exees T(s', a', ( (R(s', a', 8) + +V(("")
While one is tempted to solve our MDP using off-the-shelf approaches such as value iteration Pashenkova et al., 1996) to learn an optimal response selection policy, these approaches are in- feasible in our problem setting due to the tremendous number of possible conversations between a human user and the LLM (i.e., huge number of states and actions).
3 MONTE CARLO TREE SEARCH (MCTS) FOR CONVERSATION PLANNING
3.1 DESCRIPTION OF VANILLA MCTS
More recently, simulation-based planning algorithms like MCTS (Browne et al. 2012) have shown success in tackling MDPs surrounding language-based tasks (Yu et al. 2023 Koh et al.) 2024) by planning around more promising actions and states. MCTS uses a simulate attor of the environment to explore future states and actions, using observed cumulative rewards from simulation to learn state- action values via Q-function ((s, a) (Mnih et al. 2013) Watkins & Dayan, 1992). The state-action value approximates the expected cumulative reward that can be achieved by action a at state s.
Our approach, SCOPE, uses MCTS as its backbone. Here, we provide brief overview of MCTS (details can be found in Appendix [A.)). In MCTS, we assume access to budget of K itera- tions. At iteration & during the selection phase, we traverse a search tree from the starting state according to the Upper-confidence Tree (UCT) (Galván & Simpson (02I) tree-search policy:
where Qx is the state-action value estimate of selecting action at state during iteration k, N&(s) is the number of times visited, N& a) is the number times action a has been selected at 8, and À is constant which encourages exploration when selecting actions. With the ubiquitous success of LLMs, using an ex- ternal LLM as a simulator of human user (Yu et al. 2023 Yao et al. 2024) has become a popular way to perform simulation rollouts in MCTS (although we argue in the next section that doing so is impractical). Finally, the state-action value is updated with observed cumulative reward R (with dis- count factor 7) the end of iteration via Qu,s, a) Q a) 1/Ne(s, a)) R//N (s, a). From hereon, we refer to the procedure of MCTS with an external LLM simulator as vanilla MCTS.
(s)) arg max.eA (Q)(s. Avolog (M(ss)/N((ss))
3.2 BOTTLENECK FOR REAL-TIME CONVERSATION PLANNING
While MCTS has shown promising results in games such as Go (Silver et al. 2016 and Hearthstone (Swiechosski al., 2018), 3, it is impractical for real-time conversation planning as it requires large planning budget to simulate future conversations. In particular, performing multiple simulation roll- outs at every conversation turn with an external L.M acting as a human user simulator requires a large number of LLM inferences (or API calls to an LLM service provider, such as ChatGPT (Ope- nAl 2023). ). Using an LLM to simulate a conversation with responses of reasonable length takes few seconds. So, the key bottleneck is that we cannot perform sufficient number of simulation rollouts (a key step in the MCTS algorithm) within a reasonable amount of time. As we can only simulate very narrow scope of search space, we cannot accurately estimate state-action values to select the optimal LLM response at every turn. Interestingly, we note that many prior simulation- based planning approaches for L.MSs (Koh et al. 2024 Jang al. 2021 Zhou et al., 2024a use
4

---

Published as a conference paper at ICLR 2025
large amount of time to plan effectively during runtime. In fact, results from et al. (2023) showed that 740 seconds search time (at each conversation turn) is needed for vanilla MCTS to achieve reasonable planning performance in goal-oriented dialogue task. This is clearly unreasonable for any real-time conversation constrained by a small window of response time. Indeed, our experi- ments (Section 6.3) show that vanilla MCTS is ineffective for conversation planning under realistic planning budgets. To overcome this bottleneck, we introduce SCOPE in the next section, novel approach which exploits conversation semanties avoid costly simulations with LLM queries.
4 INTRODUCING SCOPE
The key intuition behind SCOPE is to perform MCTS without explicitly simulating future conversa- tions with costly LLM queries. To do so, we leverage dense semantic representations (Devlin et al.) 2019 [eee al. 2024| Rui et al. 2024 Lau al. 2024a) of natural language in a continuous space which we refer to as semantic space. Notably, we found that a conversation can be captured effec- tively by series of stochastic transitions in the semantic space (we provide empirical evidence in Appendix[A.8 A across multiple turns. By predicting these transitions and learning the instantaneous rewards associated with each point in semantic space, we can perform MCTS with simulations se- mantic space instead of using time- conemonnumnng LLM queries. This results in a non-myopic approach that selects the optimal LLM responses in real-time conversations. While prior state abstraction works (Hostetler et al. 2014) have tried to cluster MDP states based on feature similarities, they still rely on costly simulations the original environment. On the contrary, our approach performs simulations entirely in the semantic space, which are much less time-consuming.
SCOPE consists of two distinct phases (Figure D. During the learning phase, we use static conver- sation data to learn lightweight transition and reward model over the semantic space. Both models are significantly faster to query as compared to LLMs, as only a single forward pass of the model required to simulate each conversation transition. The transition model (Section 4.2) predicts how a conversation transitions stochastically from one point to another in the semantic space while the reward model (Section 4.3) predicts the reward associated with each point in semantic space. Therefore, every conversation can be represented as path in this semantic space, and our goal is to search for the optimal next immediate action that leads a path with the highest cumulative reward. We provide several examples of such paths in Figures 3a and 3c During runtime, SCOPE uses semantic embedding model to project the conversation starter and candidate LLM responses into the semantic space. Then, SCOPE uses the learnt models from the learning phase to broaden the scope of search in semantic space (Algorithm]] T without any need for additional LLM queries. Our experiments (Section 6.3) show that under different planning budgets, SCOPE consistently achieves higher cumulative rewards than other basclines.
4.1 SEMANTIC SPACE REPRESENTATION
We use semantic embedding model S R" to map conversation states into its semantic representation ă A [()). In practice, we can use of-the-shelf text embedding models as f. With this, we rewrite the original MDP (T) for conversation planning into
arg maxa Σx T (3.0.3)) [R(S,,
+
(3)
where T' is the transition model over semantic space, R is the instantaneous reward associated with each conversation turn in semantic space, V is defined recursively similar Equation ( and 3' is the resulting state in semantic space after a transition. In this new MDP, state ä represents point in semantic space, represents an action (possible L.M response) in the semantic space. A conversation's is semantic transition ă + 3' is represented as a directional vector along a path shown in Figure I We theoretically show in Appendix A.3 that under some assumptions of f. R and T. new MDP Equation (3) yields the same solution as the original MDP Equation (I). By learning T and R using static conversation data (details covered next), SCOPE performs MCTS in the Th" semantic space to solve MDP Equation (3) without needing costly LLM queries. In our experiments, we show that even if assumptions on f. R and T do not hold true, SCOPE consistently outperforms other baselines by selecting L.IM responses that yield higher cumulative rewards.
5

---

Published as a conference paper at ICLR 2025
4.2 LEARNING TRANSITION MODEL T IN SEMANTIC SPACE
Given a semantic embedding model ʃ S + R", our first step is to learn a transition model T55, ā, 5'), allowing us to simulate transitions in semantic space (we do not necessarily need to de- rive the transition probability explicitly). To do so, we make use of a conversation dataset containing N traansiiion::
s'y); where 8;, s/ represents an observed transition from {(s1, s1), (22, $2)..... ......................... (sN,
one conversation state to another. For example, the sentence pair: (1) "Human: Hello how are you?" and (2) "Human: Hello how how are you? LLM: I' I'm good, thank you! What did you do this week- end? Human: I went to the cinema!" represents a transition at one conversation turn ("I'm Imm good, thank you! What did you do this weekend?" is action a taken by the LLM). Next, use seman- tic embedding model f to transform this dataset into {( 31), (3 32).....
...,. (á 8'y) Ideally, a learnt T should allow us to sample semantic transitions similar to those found in the dataset.
At first glance, one might treat this as a multi multi-output regression problem in supervised learning setting (given labeled dataset of conversation transitions) and learn a deterministic neural network (5 0T): ): IR"" ++ R." with network weights Or according to the mean squared error loss:
mino, N- Σ (Fr(s,, 0r) =()
that approximates transitions from T. However, this neural network. being deterministic, cannot simulate the stochastic nature of transitions within conversations. Instead, we can use probabilis- tic models such mixture density network (MDN) (Bishop) 1994) or deep ensembles (Lepikhin
al. 2021 to model T a, based the labeled dataset. These probabilistic models are more suitable largely due to their abilities to draw samples from transition distributions (more details in Appendix A.6). We provide empirical evidence that these probabilistic models can indeed model stochastic semantic transitions well in Appendix A.8 While it is not immediately clear which prob- abilistic model choice of (s, 0r) leads to better performance in SCOPE, we perform ablation studies in Section 6.4 tease out the influence of different transition model choices on performance of SCOPE. Note that in our implementation, T consists of two separate models, one to predict 8 - à and another to predict (3, â) + s' in semantic space (details in Appendix A.6).
4.3 LEARNING REWARD MODEL R IN SEMANTIC SPACE
In the original problem setting, it is easy to derive the instantaneous reward R(s, s') of Equa- tion (T) at each conversation turn. For example, we want to minimize the number of harmful words uttered over the entire conversation, we can simply count the number of harmful words appearing each conversation turn and treat that as the instantaneous reward during simulation in MCTS. How- ever, as SCOPE performs MCTS in the semantic space, we cannot directly derive the instantaneous reward during simulation because we do not know the reward as we transition from one point to another in semantic space. To resolve this, we use another neural network (R (R)), parameterized by 2R. to estimate the reward associated with every point ø in the semantic space. Then, for any in semantic space, the instantaneous reward in semantic space R(, a, (Equation (3) can be recovered via R(3 ā, 3') ze FR((', RR) - FR @R) (this an approximation if the neural network cannot learn the rewards perfectly). We provide rigorous explanation on the validity of this recovery process and details of the training process for the reward model (R ²R) from data supervised setting Appendix A.4 Note that in practice, we can avoid training reward model and directly use off-the-shelf models by using the same model for reward and semantic embedding (details in Section 6.2and and Appendix A.6
state s' encountered after performing
USING SCOPE DURING RUNTIME
As we show in our experiments (Section 6.33 the learning phase only needs to be conducted once to learn T and R before deploying them for different real-time conversations. During runtime, SCOPE uses the same learnt transition and reward models T, R to perform MCTS (similar to that in Section 3) in semantic space. Algorithm demonstrates SCOPE at every conversation turn.
Given a conversation context Sinit ending with a prompt from a human user, the LLM, like prior works (Kambhampati et al. 2024 Yang et al. 2024), proposes list of candidate L.M responses

---

Published as a conference paper at ICLR 2025
Algorithm Semantic space Conversation Planning with improved Efficiency (SCOPE)
1: Input: Initial conversation context Sinit. Transition model T and reward model R from learning
phase (Sections 4.2 and 4.3) Pre-trained semantic embedding model f. k - 0. Initial Q- function (x à Planning budget K. Branching factor m. Search depth D.
2: Propose m candidate LLM responses: {a1. 02..... am) J.
3: Projection to semantic space: mii - f ((mma) 0j (Sii + +a2) [(mmi) Vj 1,2,
4: while & < do
5: Select From root iniits traverse search tree according to search policy (3)
arg maxa (Qk(3, + + UCT(3 a)) until leaf state & with unexplored action is reached.
6: At teaf. pick random unexplored action 0jeat-
7:
Expand Conditioned on the selected action atat randomly sample a new state nnw from learnt transition model 7 to simulate T ttear) + new At new state $ &nww. Use T to sample m state actions neww ...... , new and assign them 5 new (details in Appendix (
8:
Simulation Run simulation rollouts from new by sampling from T until termination at search depth D, taking note of observed cumulative rewards R using R.
9:
Update Backpropagate observed cumulative rewards ft to each encountered state in search tree and update state-action values via (K+1 = (x ā) 1/Nx(B)) + R/Na(B, a).
10:
= ++1
11:
end while
12:
Return LLM response with largest state-action value: arg maxa "q.......... Q (iints ā
(line 2). Then, project Sinit and the candidate responses semantic space with the help of pre- trained semantic embedding model f. The projected candidate actions a, (line 3) corresponds to the semantic representations of the LLM response, proposed by the specific LLM being used. As different LLMs would typically propose different starting candidate responses even with the same prior dialogue states, this captures the behavior of the specific LLM being used, which will result in different simulation outcomes for different LLMs. From line 4 to 9, SCOPE runs MCTS in the semantic space with the trained 7 (from Section 4.2) acting as a simulator until search depth D. The cumulative rewards consists of the sum of discounted instantaneous reward given by reward model R (Section 4.3) and is used to update Q-function Q â) after each simulation rollout. In Section 6.4 we conduct some ablation studies to investigate the effect of different transition model choices and search depth D).
Once planning budget K is exhausted, we use the learnt Q-function (x â) to select the best LLM response (Line 11) to be shown to the human user. After the human user replies, we repeat SCOPE in the next conversation turn. In practice, we use time the planning budget (instead of fixed number of algorithm iteration K) and run SCOPE for the given amount of time for real-time conversations. A detailed visual guide of Algorithm can be found in AppendixAA.. A.7
EXPERIMENTS
We evaluate SCOPE on large variety of conversation starters from dialogue datasets consisting of open conversations and dialogues between LLM and humans (Zheng et al. 2024 Li et al.) 2017) and compare its performance with variety of conversation planning baselines (details in Appendix[A.11 A.II. First, show that for two practical reward functions, SCOPE attains larger cu- mulative rewards as compared to other planning algorithms under practical planning budget during runtime. Then, we perform multiple ablation studies to tease out the influence of different compo- nents within SCOPE.
6.1 CHOICE OF REWARD FUNCTIONS
We perform our experiments on two practical reward functions: cumulative length human re- sponses in conversation (measured by tokens) and the cumulative harmful score of conversation (we treat the negative of this harmful score as the reward to be maximized). These reward functions practical in real-world settings for a few reasons. Selecting L.M responses that maximizes the

---

Published as a conference paper at ICLR 2025
(expected) cumulative length of human responses in conversation serves as surrogate metric for the engagement of a human user in that conversation and therefore is of practical interest to com- mercial LLM owners. Furthermore. longer cumulative human response length also implies greater commercial benefits, since many LLM service providers charge based on token count. In addition, it is also of regulatory interest minimize the harmful content of conversation as whole, pecially when LLMs are deployed as chatbots across different age groups. In our experiments, we use Llama Guard 2 (Meta) 2024) measure how safe (conversely, how harmful) conversation is. Furthermore, we note that both reward functions are dependent on the human user's response. Therefore, this serves as a challenging task because we need to take into account the stochastic transitions within conversation and long-term rewards to perform conversation planning well. We provide further discussion and examples of some other practical reward functions in Appendix AA55
6.2 EXPERIMENTAL SETUP
To project conversation states and responses into a semantic space as detailed in Section 4.1 we use the feature layer of Llama Guard 2 (Meta 2024) the semantic embedding. During the learning phase, we use conversation data from (Zheng et al. 2024) to train the transition and reward model in semantic space using the techniques introduced in Sections 4.2 and 4.3 Notably, only perform the learning phase once and reuse the learnt models for different conversation starters during evalu- ation. This is similar to real-world deployment for conversational agents: an LLM owner uses large amount of existing conversation data to learn transition and reward models over semantic space once before deploying these models to perform SCOPE for different conversations during runtime.
During runtime evaluation, we use an LLM to propose set of candidate responses (i.e., actions) for a conversation starter. We then project the conversation starter and candidate actions into the semantic space representations (as introduced in Section 4.1 and perform SCOPE to learn the Q- function. Finally, we use state-action values from the Q-function to select the best L.M response to show the human user after performing SCOPE. During evaluation, emulate a human user's response, progressing the conversation to the next turn. This repeats for conversation turns and the evaluation reward is derived from the final conversation using the reward function. A more detailed explanation of our experimental setup and design choices is provided in Appendix A.1I for ease of reproducibility of results.
evaluation LLM to
6.3
MAIN RESULTS
We compare SCOPE with several conversation planning baselines. Random selects a response ran- domly from the pool of LLM candidate responses, without considering any rewards. 1-step Greedy uses the reward function and one step human user simulation (with an external LLM) to select an LLM response that yields the highest instantaneous reward. We also consider 0-step Greedy, an even greedier approach where the LLM response is selected without any look-ahead simulation (also known rejection sampling in some reinforeement learning (RL) works). Vanilla MCTS adopts a tree-search planning approach similar to those found in Yu et al. 2023; Koh et al., 2024) and uses large amount of L.LM queries for look-ahead simulation in vanilla MCTS. We provide detailed implementation of each method in Appendix 1T for reproducibility.
SCOPE achieves higher cumulative rewards than other baselines. Figures 3a and 3b show that SCOPE achieves higher cumulative rewards than other baselines within 3 seconds of planning time. In partieular, SCOPE non-myopic, performing planning in semantic space and hence outperforms myopic approaches like 0-step Greedy and 1-step Greedy because it takes into account the stochas- tic transitions within conversation to infer long-term rewards. addition, SCOPE also outperforms conventional planning algorithms like vanilla MCTS (Yu et al., (023). This corroborates our claim in Section 3.2 that vanilla MCTS can only perform simulation within a very narrow scope under realistic amount of planning budget and therefore performs poorly. In fact, we do not see an in- crease in rewards gained when vanilla MCTS is allocated a few more seconds of planning time; this suggests that vanilla MCTS requires so much budget to plan effectively that a few additional seconds of plamning budget does not matter. On the contrary, SCOPE, without requiring costly LLM queries, can perform simulation in semantic space much faster under realistic planning budget. As such, the rewards achieved by SCOPE increases with only a slight increase (a few seconds) in plan- ning budget. Our results can also be interpreted quantitatively by L.M owners: Figure 3h implies
8

---

Published as a conference paper at ICLR 2025
greedy caatie
IHP pracy (anko VCTS
Conversaton on from SCORE
Conversation from SCORE
Canuemation from Grmedy Low raars region High reword rogio"
Comveration from Sreedy
Curradto FUAIET
200
Low sinrrd region
High reword rogion
20-
03
-10
10
3.5
3.0
2.0
budgget
(a) Harmfulness
(b) Human response length
(c) Harmfulness
(d) Human response length
Figure 3: (a) and (b) show the average cumulative rewards (higher is better) gathered by SCOPE compared to other baselines over 100 different conversation starters for the harmfulness and human response length reward function over conversation turns. The z-axis shows the effect of increased planning budget (time). (c) and (d) show visualization of a conversation generated from SCOPE and 1-step Greedy in the semantic space.
that SCOPE achieves conversations (spanning 5 turns) where human responses are, average. 150 tokens longer. This can be used by LLM owners to tie in with business metrics such as application engagement and customer interest.
Visualization of conversations generated semantic space. Figures 3c and 3d show examples of conversations generated via SCOPE in semantic space (reduced lower dimensional space with I-SNE (Van der Maaten & Hinton 2008) w.r.t. both reward functions. Expectedly, the conversation path produced by SCOPE (cyan path) passes through regions with higher rewards. On the other hand, conversation path from myopic approaches (i.e., greedy) ends up in regions with low rewards (e.g., red path on the left of Figure 3c). This suggests that SCOPE exploits conversation transitions in the semantic space to account for long-term rewards, selecting better LLM responses. Myopic approaches cannot do so. Lastly, we provide some qualitative examples of L.LM responses selected by SCOPE and other methods during each conversation evaluation in Appendix A2 These quali- tative examples provide insights as to why SCOPE selects LLM responses better than other methods.
Shep preees
stop grady
soop greedy
budget)
budgett
SCAFE
SCOPC
(a) Harmfulness
(b) Human response length
Figure 4: Comparison of SCOPE with larger planning budget vanilla MCTS (higher is better).
SCOPE plans 70 times faster than vanilla MCTS. Figure shows how SCOPE fares against vanilla MCTS under higher planning budget (around 70 times longer planning time). We show that SCOPE (green line), under a realistic planning budget of 1 second, achieves larger rewards than vanilla MCTS even when the latter is allocated planning budget of 70 seconds. This suggests that conventional simulation-basee to the use of excessive LLM queries for look-ahead simulations. Thus, even at higher planning budgets, vanilla MCTS can only perform simulation within a narrow scope and cannot achieve higher cumulative rewards than SCOPE. In Appendix(A.Il IA.10 show that each simulation rollout in SCOPE takes 92 times faster than that in vanilla MCTS, and serves as the main reason why SCOPE able to plan much faster, achieving better cumulative rewards in real-time conversations.
planning algorithm indeed require large planning budget due

---

Published as a conference paper at ICLR 2025
UFWEY MUTE
IEB SPWBy MCT HOO
Hee oweer
Uie SCORC3
2.01
203
SOO HDM
20-
00
100
10
L5
3.5
10
1.
2.5
25
31
1.0
2.8 31
1.0
200
3.0
(a) Harmfulness
(b) Length
(c) Harmfulness
(d) Length
Figure 5: (a) and (b): Ablation study on how transition model choice affects SCOPE's performance.
SCOPE-DE DE uses deep ensembles (Lepikhin et al., (221)) while SCOPE-MDN uses MDNs (Bishop)
1994 (c) and (d): Ablation study on how search depth affect SCOPE's performance.
6.4 ABLATION STUDY
We also conduct ablation studies shown in Figure5]ue tease out the influence of various components in SCOPE. In Figures Sa and [56] we investigate the effect of different transition models on SCOPE. In Figures and and 5d we investigate the effect of varying search depth D (introduced in Algorithm I on SCOPE. To reduce plot clutter, we removed performance of vanilla MCTS and Random from the figures because they tend to do worse than greedy approaches.
1994) and deep en- sembles (Lakshminarayanan et 2017) model choices for T. More details on these models can be found in Appendix A.6 Figure 5b shows that for human response length, the choice of transition model T does not influence SCOPE's performance much. On the other hand, Figure 5a shows that for the harmful reward function, SCOPE with deep ensembles generally outperforms MDN, sug- gesting that MDN might not learn well and is susceptible to training instability and model collapse (Makansi et al. 2019). An important point to note is that the prediction quality of a transition model (w..t. the training conversation dataset) is not accurate indicator of SCOPE's performance whole. From literature (Chen et al.] 2024), it is difficult to pinpoint the exact influence of a single component (e.g., transition model) sion on the relationship between transition model's local prediction quality and SCOPE's overall performance in Appendix A.9
Effect of different model choices of T on SCOPE. We used MDN (Bishop
overall algorithm like SCOPE. We provide more discus-
Effect of varying search depths. Figures 5e and [dd show that larger search depths generally im- prove the performance of SCOPE across different planning budgets. This suggests that larger search depths allow SCOPE to simulate longer conversations in semantic space, inferring rewards gathered across higher number of conversation turns. Conversely, when the search depth small (red line), SCOPE suffers from poor performance because it cannot plan effectively for rewards in later conver- sation turns. Interestingly, we observe that the effect of search depth seems to plateau a depth of conversation turns (i.e., blue, green, and black lines have comparable performance). This suggests that SCOPE does not have to search too deeply to infer how good an LLM response is.
7 CONCLUSION
Our paper presents SCOPE, a novel approach which exploits compact semantic representation of conversations to learn stochastic transitions of conversation and their associated rewards in semantic space. During runtime, SCOPE uses MCTS to plan entirely semantic space at broader scope without needing additional LLM queries. We show that SCOPE attains larger cumulative rewards as compared to other simulation- based baselines in our experiments. Our work removes the need to use costly L.MM queries for simulation and presents a paradigm shift from conventional simulation-based conversation planning. In addition, one limitation of SCOPE is that we kept our transition models fixed, and did not account for different behaviors of different LLM models. Adapting SCOPE to different LLM models during deployment is promising future research direction and could bring further performance gains (some possible improvements are discussed in aopendix[A.6)
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY
We have released our code in the GitHub link: httts:///itthu:: http:/hhuu..ooccchhhhchhe h convo-plan-Seee SCOPE) for reproducibility of experiments. The experimental setup, models, prompts used for LLMs and hardware can be found in Section 6.2 and Appendices A.6 and A.11
ACKNOWLEDGMENT
This research is supported by the National Research Foundation Singapore and the Singapore Min- istry of Digital Development and Innovation, National AI Group under the AI Visiting Professor- ship Programme (award number AIVP-2024-001). Zhiliang Chen is supported by the Institute for Infocomm Research of Agency for Science, Technology and Research (A*R). Xinyuan Niu is supported by the Centre for Frontier AI Research of Agency for Science, Technology and Research (TAR).... We would like acknowledge that computational work involved in this research was partially supported by NUS IT's Research Computing group using grant numbers NUSREC-HPC. 00001.
REFERENCES
AI@ Meta. Llama model card. 2024. URL httpps://giihub..cc//mtttea 1lama3/b ma www./mannnnnn/ m/MODEL CARD md
Ron Amit, Ron Meir, and Kamil Ciosek. Discount factor as regularizer in reinforcement learning. In Proc. ICML., 2020.
Richard Bellman. markovian decision process. Journal of muthematics and mechanics, pp. 679- 684, 1957.
Christopher M Bishop. Mixture density networks. 1994.
Cameron B Browne, Edward Powley, Danicl Whitehouse, Simon M Lucas, Peter I Cowling. Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1): 43, 2012.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proc. 2020.
Zhiliang Chen, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Towards AutoAl: Optimizing machine learning system with black-box and differentiable components. In Proc. ICML, 2024.
Zhiliang Chen, Gregory Kang Ruey Lau, Chuan-Shema Foo, and Bryan Kian Hsiang Low. Duet: Optimizing training data mixtures via feedback from unseen evaluation tasks, arXiv:2502.00270, 2025.
Sumit Kumar Dam, Choong Seon Hong, Yu Qiao, and Chaoning Zhang. A complete survey on LLM-based Al chatbots. 10Xx::2406.16337, 2024.
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv:/810.04800. 2019.
Edgar Galván and Gavin Simpson. On the evolution of the mets upper confidence bounds for trees by means of evolutionary algorithms in the game of carcassonne. In Proc. IEEE SSCI, 2021.
Shibo Hao, Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In Proc. EMNLP. 2023.
Jesse Hostetler, Alan Fern, and Tom Dietterich. State aggregation in Monte Carlo tree search. In Proc. AAAI, 2014.
Ronald Howard. Dynamic Probabilistic Systems, Volume I: Markov Models. Courier Corporation, 2012.
11

---

Published as a conference paper at ICLR 2025
Youngsoo Jang, Seokin Seo, Jongmin Lee, and Kee-Eung Kim. Monte-carlo planning and learning with language action value estimates. In Proc. ICLR, 2021.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks. In Proc. ICML, 2024.
Byoungjip Kim, Youngsoo Jang, Lajanugen Logeswaran, Geon-Hyeong Kim, Yu Jin Kim, Honglak Lee, and Moontae Lee. Prospector: Improving LLM agents with self-asking and trajectory rank- ing. In Proc. NeurIPS, 2024.
Jing Yu Koh, Stephen McAlerr, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents, arXivv2407.01477, 2024.
Deepak Kumar, Yousef AbuHashem, and Zakir Durumeric. Watch your language: Investigating content moderation with large language models. In Proc. ICWSM, 2024.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Proc. NeurIPS, 2017.
Gregory Kang Ruey Lau, Wenyang Hu, Liu Diwen, Chen Jizhuo, See-Kiong Ng, and Bryan Kian Hsiang Low. Dipper: Diversity in prompts for producing large language model ensem- bles in reasoning tasks. In NeurlPS 2024 Workshop on Foundation Model Interventions (MINT), 2024a.
Gregory Kang Ruey Lau, Xinyuan Niu, Hieu Dao, Jiangwei Chen, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Waterfall: Scalable framework for robust text watermarking and provenance for LLMs. In Pruc. EMNLP, 2024b.
Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer, Jeremy R. Cole, Kai Hui, Michael Boratko, Rajvi Kapadia, Wen Ding, Yi Luan, Sai Meher Karthik Duddu, Gustavo Hernandez Abrego, Weiqiang Shi, Nithi Gupta, Aditya Kusupati, Prateek Jain, Siddhartha Reddy Jonnala- gadda, Ming- Wei Chang, and Iftekhar Naim. Gecko: Versatile text embeddings distilled from large language models. 2403iv:200..2000 2024.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. GShard: Scaling giant models with conditional computation and automatic sharding. In Proc. ICLR, 2021.
Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu. Dailydialog: A manually labelled multi-turn dialogue dataset. In Proc. IJCNLP, 2017.
Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Use your INSTINCT: INSTruction optimization for LLMs using Neural bandits Coupled with Transformers. arXiv:2310.02905 2024.
Ryan Liu, Howard Yen, Raja Marjieh, Thomas I.. Griffiths, and Ranjay Krishna. Improving in- terpersonal communication by simulating audicnces with language models. arX0v:2311.00687, 2023.
Osama Makansi, Eddy Ilg, Ozgun Cicek, and Thomas Brox. Overcoming limitations of mixture density networks: A sampling and fitting framework for multimodal future prediction. In Proc. CVPR, 2019.
Meta. Meta Llama Guard 2024.
Mistral. Mistral NeMo. 2024.
URL https://hugiinnfaccccc///ttttll
Mistra Nemo- Ins.-utt-ttuut2077
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv:1312.5602, 2013.
OpenAl. GPT-4 technical report, 2023.
12

---

Published as a conference paper at ICLR 2025
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kel- ton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Proc. NeurlPS, 2022.
Elena Pashenkova, Irina Rish, and Rina Dechter. Value iteration and policy iteration algorithms for markov decision problem. In AAA/'96: Workshop on Structural Issues in Planning and Temporal Reasoning, 1996.
Rui Qiao, Zhaoxuan Wu, Jingtan Wang, Pang Wei Koh, and Bryan Kian Hsiang Low. Group-robust sample reweighting for subpopulation shifts via influence functions. In Proc. ICLR, 2025.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. arXiv:2305. 2023.
Desik Rengarajan, Gargi Vaidya, Akshay Sarvesh, Dileep Kalathil, and Srinivas Shakkot- tai. Reinforcement learning with sparse rewards using guidance from offline demonstration. arXiv:2202.04628, 2022.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. In Proc. NeurIPS, 2019.
Meng Rui, Liu Ye, Shafiq Rayhan Joty, Xiong Caiming, Zhou Yingbo, and Yavuz Semih. SFR- embedding- mistral: Enhance text retrieval with transfer learning. Salesforce Al Research Blog, 2024.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484-488 2016.
Maciej Swiechowski, Tomasz Tajmajer, and Andrzej Janusz. Improving hearthstone ai by combining mets and supervised learning algorithms. In Proc. CIG, 2018.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of machine learning research, 9(1)), 2008
Ashwin Vijayakumar, Michael Cogswell, Ramprasath Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. Diverse beam search: Decoding diverse solutions from neural se- quence models. arXiv preprint 1rXiv:1610.02224. 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
Zhaoxuan Wu, Xiaoqiang Lin, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Prompt optimization with EASE? Efficient ordering- automated selection of exemplars. arXiv:2405. 16/22, 2024.
Tianbao Xie, Siheng Zhao, Chen Henry Wu, Yitao Liu, Qian Luo, Victor Zhong, Yanchao Yang. and Tao Yu. Text2reward: Reward shaping with language models for reinforcement learning. In Proc. ICLR, 2024.
Xinyi Xu, Zhaoxuan Wu, Rui Qiao, Arun Verma, Yao Shu, Jingtan Wang, Xinyuan Niu, Zhen- feng He, Jiangwei Chen, Zijian Zhou, Gregory Kang Ruey Lau, Hieu Dao, Lucas Agussurja, Rachael Hwee Ling Sim, Xiaoqiang Lin, Wenyang Hu, Zhongxiang Dai, Pang Wei Koh, and Bryan Kian Hsiang Low. Position paper: Data-centric Al in the age of large language models. In Proc. EMNLP Findings, 2024.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoe V. Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. Proc. ICLR, 2024.
Yuchen Yang, Houqiang Li, Yanfeng Wang, and Yu Wang. Improving the reliability of large lan- guage models by leveraging uncertainty-aware in-context learning. arXiv:23/0004782, 2023.
13

---

Published as a conference paper at ICLR 2025
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Proc. NeurlPS, 2024.
Xiao Yu, Maximillian Chen, and Zhou Yu. Prompt-based Monte-Carlo search for goal-oriented dialogue policy planning. In Proc. EMNLP, 2023.
Jinghan Zhang, Xiting Wang, Yiqiao Jin, Changyu Chen, Xinhao Zhang, and Kunpeng Liu. Proto- typical reward network for data-efficient RLHF, arXiv:2406. 06606, 2024.
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning. In Proc. NeurlPS, 2023.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang. Zhuohan Li, Zi Lin, Eric P. Xing, Joseph E. Gonzalez. Ion Stoica, and Hao Zhang. LMSYS-Chat-IMS A large-scale real-world LLM conversation dataset. In Proc. ICLR, 2024.
Andy Zhou, Kai Yan, Michal Shlapentokh-Rone Rothmmn,, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. In Proc. JCML, 2024a.
Zijian Zhou, Xiaoqiang Lin, Xinyi Xu, Alok Prakash, Daniela Rus, and Bryan Kian Hsiang Low. DETAIL: Task DEmons EEmonsTration Tration Attribution for Interpretable In-context Learning. In Proc. NeurIPS, 2024b.
14

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 MYOPIC APPROACHES CANNOT DO CONVERSATION PLANNING
In this subsection, provide illustrative example why myopic approaches cannot select the optimal LLM response. In Figure 6 there are two candidate LLM responses (A and B) for the human user's prompt. Here, goal minimize the harmful content of the overall conversation. we simply adopt a myopic approach and check the harmful content of LLM response A and B with toxic classifier such Llama-guard (Meta 2024), both responses are deemed harmless and we could choose either of the LLM responses to show to the user. However, we perform look- ahead simulation of future conversations (with simulator of the human user, possibly with an LLM or a lightweight transition model T' introduced in our paper), we find that LLM response has probability of causing the human user to produce harmful content, leading to harmful conversations. This arises due to close semantics between "vapes" and "drugs" in conversation setting (and, our conversation simulator reasons that it is possible that the topic of drugs might arise in future conversations).
buy
Singspore?
What lind of parthhment belking
foe adductive
Tell me anothe fact ibout Sinpeoore.
What
LLM response A: Singapore
LLM response B: Singapore has
known for its
cleanliness and strict anti-
laws against electronic cigarettes and vapes
littering laws
Hammiu topis
Can you tell me fact about the law of Singapore, where ICLR 2025 will be held?
Figure 6: Myopic approaches cannot discern whether LLM response A and B lead to safer conversa- tions. However, conversation planning reasons about future transitions with look-ahead simulations and selects LLM response A because it leads safer conversations.
A.2 OVERVIEW OF MONTE CARLO TREE SEARCH (MCTS)
Our approach, SCOPE, uses MCTS as its backbone. MCTS, we assume access to a budget of K iterations and each iteration consists of four phases: selection, expansion, simulation, and update. At iteration & during the selection phase, we traverse a search tree from the starting state according to the Upper-confidence Tree (UCT) (Galván & Simpson 202T) tree-search policy:
(s)) arg max.E (Q)(s,a) >v (log (x(s))/Na((.) (s) where Qx (s, is the state-action value estimate of selecting action at state a during iteration k (s) is the number of times is visited, N&(s, a) the number of times action a has been selected s, and À is a constant which en- courages exploration when selecting actions. This continues until an unexplored action is chosen at leaf state. During expansion, we perform simulation for single conversation turn with the unex- plored action and add the resulting new state to the search tree. Then, we perform simulation rollout from the new state using randomly selected LLM responses and human user simulation until termi- nation (c.g., certain conversation depth). With the ubiquitous success of LLMs, using external LLM as a simulator of human user (Yu et al. 2023 Yao et al. 2024) has become a popular way to perform simulation in MCTS (although argue in the next section that doing is impractical). Fi- nally, the state-action value is updated with observed cumulative reward R (with discount factor
15

---

Published as a conference paper at ICLR 2025
at the end of iteration k via Qx(s.a) - - The MCTS pro- cess repeats for K iterations and the action with the highest state-action value: arg max, Qk(s, a) executed. In conversation setting,
LLM to generate the initial pool of candidate LLM responses, in which we select the one with the highest state-action value after performing MCTS.
A.3 PROOF OF MDP TRANSFORMATION IN SEMANTIC SPACE
We show that Equations ① and (3 are equivalent in the following proposition.
Proposition A.1. Let f Tied + IR. be bijective semantic embedding function. Let s, E TRd RR, R be that defined in Section 4. and V,T, be the value, transition and reward function defined in Section 2.1 Assume there exists RRxXX* + R and R Raxxxa + R such that T(,,ū, 8') T(s, a, s') and R(s,ū,8
ā,3') ) R(s, a, s') for E R. , E RR, ,aa E TR.. Then an action a state achieves the highest cumulative reward for original MDP
0= - arg max
(5)
and only if the same action's semantic representation (defined in Section 4.1 Ty is also the solution for MDP in semantic space:
Maa)) - ā" arg max TT ā,8) +7V(5'),,
where V(8) is recursively defined similar to Equation
Proof. Proposition A. can be proven by using the assumption that 7 = T and R R in their respective domains. That is, even after projecting states and actions into the semantic space, the transition probability and reward values are the same. Hence, the original MDP problem can be rewritten as:
arg max Σ T(s.a, >V((')))
Σ
arg max
arg max Σ (R(3,
arg max
where (1)
uses the assumption that 7(8, a, 8') T(s, s') and R(5,0,8') = R(s s'), uses
the recursive definition of state value: v(8) V(s). Lastly, holds true because ā f(a), fs), and we have assumed that function f is bijective. Therefore, we have shown that both MDPs are identical.
Interestingly, the assumptions of = R and bijective f of this MDP transformation in semantic space have real-world interpretations. T T, R R implies that we can leamn transition and reward model in semantic space (as detailed in Sections 4.2 and (43) represent rewards and transitions of conversations in semantic space perfectly. A bijective implies that every possible natural language conversation can be projected to a unique point in semantic space. In practice, might be impossible to learn these models perfectly (due to noise in data, training imperfections or information loss from semantic representations) in semantic space. Despite this, our empirical results in 6.c that off-the-shell modern semantic embedding model and appropriately learnt 7 and R are sufficient for SCOPE outperform conventional planning baselines.
16

---

Published as a conference paper at ICLR 2025
Table Number of questions asked by the user throughout the conversation, evaluate the engage- ment of the user in the conversations planned using the cumulative length reward function.
Random
O-step Greedy
1-step greedy
SCOPE 3s
2.99
2.97
2.95
3.31
A.4 DETAILS ON LEARNING REWARD MODEL IN SEMANTIC SPACE
In our problem setting, reward model ( nn) helps indicate us the reward associated with
each point & in semantic space. In this section, we first (a) provide details on how to train such model and (b) explain how to recover the instantaneous reward R(5 a, 5') from the learnt reward model (5 (R) when performing SCOPE.
To learn (R 0R). we first gather dataset of con- from different domains.
versations {su, $1..... &&x)
Human: you fuct about Country 2007
In our experiments, this dataset is taken from Li et al.] (2017); ZZeng et al. (2024). Notably, each datapoint 8; does not have be complete
F
versation (it can be a segment of a conversation). We first label the reward associated with each dat- apoint 9; depending on the LLM owner's use case (e.g., harmfulness, length of conversation) to ob- tain set of reward labels Yo, "/..... UNN- Reward model FR(5 OR) can then be trained over this regres- sion task via (e.g., mean-squared error) loss function ming, Ei=o( (Fr(5,, transition model in Section 4.2 the reward model is deterministic.
Country Xox cooll! that!
meous rowerd asscaattd
one stop:
6 4.f6))
y Unlike the semantic
Figure 7: How instantaneous reward is de- rived from reward model FR OR).
During SCOPE, we cannot use FR(5,; OR) directly because we need to keep track of the instan- taneous reward R(3, "(3,,,33 3') to update our Q-function part of the MCTS framework. However, because our reward model gives us the reward associated with the points 3' (after transition) and (before transition) in semantic space, their difference must indicate the change in reward caused by selecting L.MM action. Therefore, the instantaneous reward R(; a, 8') associated with conver- saton turn after taking an action à is simply the difference: R(s,ū, 55) FR(3', 0R) FR(3, OR). Figure provides intuitive illustration of this recovery process.
A.5 PRACTICAL REWARD FUNCTIONS
In experiments, used practical reward functions. The first is Llama-guard 2 (Meta 2024), which gives the harmfulness score (or inversely, the safety reward) of piece of conversation (including both LLM and human user's response). The second is simply the cumulative length of human response in a multi-turn conversation.
We selected the use of cumulative length of human response in a multi-turn conversation be surrogate metric for the engagement of human user in that conversation. To evaluate the suitability of this proxy measure, we measured 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 length rewards for planning, but during evaluation, we check if the user asking questions in the resulting conversation). We show in Table I that in conversations produced by SCOPE, the user on average asks more questions, signaling that they are more engaged with the conversation.
Other reward functions could be relevant in conversation planning. For example, one could be simply concerned if LLM responses are harmful. In this case, the instantaneous reward of an LLM taking an action a is simply the harmful score of that LLM response. Other reward functions and their effects in conversation planning are left for future research directions.
17

---

Published as a conference paper at ICLR 2025
SCOPE can be extended other language-bire based tasks in the planning domain with sufficient reward shaping (Xie et al., 2024). For example, if one is interested for an LLM to generate a sequence of language-baser based actions (i.e., LLM responses) to solve a Rubick's cube under the presence of a simulator, we can formulate this language-based problem as MDP which can be solved with SCOPE (albeit with deterministic environment). However, these problems are notoriously plagued by the sparse reward issue (Rengarajan et al., 2022) because there is only one true winning state. So, we might need to densify the reward landscape by incorporating heuristics into reward functions depending on the problem setting. Furthermore, unlike open-ended conversations, it is unclear at this point whether the language used in planning (e.g., solving a Rubick's cube) can be captured effectively by semantic representations.
We would like to emphasize that our method, SCOPE, is reward agnostic and one can use any reward function in SCOPE to plan. Other conversation engagement metrics or reward functions could be adopted by LLM providers based on their specific applications and use cases.
A.6 DETAILS ON LEARNING TRANSITION MODEL IN SEMANTIC SPACE
In our actual implementation, to approximate T (5, ",s,,,3, ā,3") we trained two different models to per- form the steps of the conversation transition in semantic space. With the two models, the transition model is able to predict the actions à (as directional vector in semantic space) that are available at a given state s, and then predict the following state s' that the conversation semantic transitions to, given ş and Ø.
The first model predicts the LLM action in semantic space & - (indicated as "human -> Ilm" in Figure 9. This approximates the LLM response to the users prompt (f(s) - f(s + a)) in the semantic space. The mean squared error of the predicted semantic action à is
N
Σ à -))(
The second model predicts the human user's next response in semantic space (),ā) + 3' (indicated as "llm -> human" in Figure().. This approximates the users follow-up response to the LLM's output (f(s + a) + f(s')) in semantic space. The mean squared error of the predicted new state 3' is
N
N
3
f(s))
As the first model represents how an LLM responds a user prompt, the model could be further fine-tuned using data collected from user interactions with the specific LLM model being deployed on, improve prediction performance.
Similarly, as the second model represents how human responds to an LLM output, this model could be fine-tuned with a specific user's demographic information or conversation history (subjected to the user's s approval and LLM provider's 's privacy guidelines), to improve its prediction performance for individual particular user.
Although this work did not explore the fine-tuning of the two models using LLM/user specific data, we believe this would be a promising future direction and SCOPE can serve as a competitive baseline and foundation for future works on such approaches in terms of performance-efficienn, trade off. For instance, the transition models could further fine-tuned with new conversational data between the user and the specific LLM these conversations come in during online deployment, to better align the model with the actual conversations that are newly collected.
We used Lmsys/ 1lmyss chat 1m dataset (Zheng et al. 2024) the dataset for training the transition models. We transform each turn of conversations into the semantic embeddings using the embedding model, and normalized each dimension of the input embedding and output target labels to mean 0 and standard deviation prior to training. The transition models were trained for 100 epochs, requiring approximately 6-8 hours train single Nvidia H100 GPU.
18

---

Published as a conference paper at ICLR 2025
Although the LLM in this dataset (lmsys/ htt/s/sssssshttllnnmeee consists of conversations mostly with the Vicuna LLM) is different from the LLM used in the experiments of this paper (Llama-3), strong empirical results show that SCOPE can generalize to different LLMs. We can also train these transition models with data mixtures from different data domains (Qiao et al. 2025 Chen al. 2025).
For the deep ensemble model (SCOPE-DE), we used an ensemble of deterministic models trained using different seeds and different train-validation splits of the conversation dataset. We used Mixture of Experts model (Lepikhin et al. 202T) as the deterministic model. 4 models were trained for each transition (action model and transition model), each with layers of experts. We used seeds 0, 1, 3 to seed the initialization and train-validation splits for the training of the transition models.
For the MDN model (SCOPE-MDN), we used K = 256 Gaussians, with the fully factored noise model (i.e., diagonal covariance matrix where the noise level for each dimension is predicted sep- arately). The model predicts the probability of each Gaussian component, well as the mean ! and standard deviation a of each Gaussian. We used seed = when training the MDN model. Typically, MDN models are trained by minimizing negative log-likelihood loss
f log (po, (ā (5)
(10)
where the likelihood of the target label under Gaussian mixture can be calculated as:
K ORPor (ālpk: Σx)
Por (āl3)
Σ
(11)
k
pêr.3 (ālpx. Ex) = exp (- (ā (xx)-)) Mi 2x (ā
1
mK)
log det Vi
(12)
However, as the embedding to harmfulness reward function was reused from the original model, included auxiliary loss during the training process to ensure good prediction both the predicted next state, and its harmfulness score. We noticed that without this auxiliary loss on the predicted reward. the predicted harmfulness score frequently differs from the true harmfulness score despite the good prediction in the transitions. Although the reward Fr((',, (e(3,0pp) (n)) is dependent on ā, where Fn((', On) R3' and R is the last layer linear transformation matrix of Lllama-uarr we treat them as independent so that the model loss will maximize the log-likelihood of both à and FR(3', OR). The new loss term can be calculated as:
L -og Σ òuper (ālpa, Ex) per.a (FR(3', (o)5''0R)]
(R))/aamm.. Kharm,k Ebarm.t) .+)
(13)
pěr,ä (FR(3', 0R) pbarm, Wbarm,
=exp (-1 (Fn(3', 0n) Mharm,
mamm, (Fn(3', (a(33',02) 0n) Mharm, 2
log det Vhamm,
(14)
where the mean and covariance of the harmfulness score is transformed with:
Phann, & R(uu + 5) Daann = RE
(15)
A.7 VISUALIZAATIO OF SCOPE
We provide a visual overview of SCOPE (Algorithm T in Figure 8 SCOPE follows the MCTS framework closely conduct conversation planning. However, the key difference between SCOPE
19

---

Published as a conference paper at ICLR 2025
Select according tree policy until an unexplored action.
Simulation keoping track rewards accumalated uaing R.
Backtrack and Update state- action valuss ((+.)).
by sampling from
Projection
"Human: Can you tell me fact about countr XXX.
Semanti projection
Line
Line
Line
Line
Figure 8: Visualization of SCOPE (Algorithm) D. which performs MCTS in semantic space with the help of semantic embedding function f. T and R (Sections 4.2 and 4.3)
and vanilla MCTS approaches is that SCOPE exploits semantic embedding function f. It and T in semantic space to perform MCTS without needing additional LLM queries.
To summarize, the key differences between SCOPE and vanilla MCTS are:
Projection. In SCOPE, we project states and actions (conversation starters and LLM re- sponses) into semantic space perform MCTS, instead of working directly with textual conversations.
Select, Expand, Simulation. In vanilla MCTS, there is clear set of actions take node in the search tree. In SCOPE, when we need to expand into a new node, we sample from the learnt transition model 7 to produce new resulting states.
Updating rewards. In vanilla MCTS, instantaneous rewards be observed directly from textual conversations. In SCOPE, we use infer rewards associated with each transition sampled from T.
A.8 SEMANTIC TRANSITION AND REWARD MODEL PERFORMANCE
In this subsection, we analyze how well we can model the stochastic transitions within conversa- tion in semantic space via T and their associated rewards via R. Figure9a that conversation between an LLM and human user can be represented by a path semantic space. This serves as a ground truth for us to learn transition model T in semantic space. Figures 9b and 9c show that after training (Section 4.2h using deep ensembles. T produces transitions similar to the ground- truth transitions. This transition model allows SCOPE perform MCTS at broader scope during runtime, learning accurate state-action values of LLM responses at each conversation turn. Note that PCA was used to project the 4096 dimensional semantic embedding to dimension of 2, Fig- ure serves to provide an illustration of the transitions of the conversation semantics. However, the relative seales and angles the vectors in this 2d projection do not represent the actual scales and angles in the higher dimensional semantic space.
To visualize how well T performs in general, plot the cosine similarity and prediction length ratio of the prediction of T' w.r.t. the ground-truth transitions in Figure 11 Our results show that in general, probabilistic model T produces average transition predictions that are similar in direction (cosine similarity, .zaxis) and of similar length (Norm ratio, y-axis) as the ground-truth transitions in semantic space. This can be seen from the high concentration predictions centred around a Norm ratio and cosine similarity of We observe that while the ensemble of models predicts direction of the transitions well (cosine-simins similarity close to 1), the predictions tend to be smaller in scale than the ground truth (Norm ratio smaller than 1). This is likely due the "averaging" effect of deterministic models trained on stochastic data. The opposite is true for the MDN models, where predictions are of relative similar scale the ground truth but are more distributed in their cosine similarity.
20

---

Published as a conference paper at ICLR 2025
PCA of conversation semantics
PCA human-silm sementics
0.050
0.05
Pred
-0.05
0.00
5um1
2
-0.05
0.00
turn1
Powd
Predi
merssnn
-0.10
mm
-0.00
tr
-0.050
SWEnO
-0.15
-0.15
-0.075
00.00
00.00
-0.175
-022
-3.3
0.3
02
-0.
-0.1
0.
5-3
0.2
0.25
0.20
0.15
0.10
0.55
0.00
Dimersion
Ormonsioon
Ommrrsion
(a) conversation transitions in the (b) Predictions of I to simulate fu- (c) Predictions of T simulate hu- semantic space
ture actions.
man responses.
Figure 9: PCA visualizations of conversation transition sin the semantic space, and the predicted
transitions by the transition model T
It can also be noted that the trained transition models predict the LLM actions (Figures 10 and (left)) better than the human responses (Figures 10 and 11 (right)). This shows that human responses tend to be more varied as compared to the L.LM actions.
Histogram plot for human->llm transitions
Histogram plot for lim->human transitions
10
10
400
120
100
2-
Norm ratio
Counts
80
200
60
0.5
0.5
40
0.2
0.2
0.1
0.1
0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Cosine Similarity
Cosine Similarity
Figure 10: Histogram plot of cosine similarity and ratio of the prediction norm for the trained semantic action (left) and transition (right) models, using MDN (Bishop 1994) as transition model choice.
Histogram plot for human->ilm transitions
Histogram plot for llm->human transitions
10
250
800
200
600
Norm ratio
Counts
150
400
0.5
0.5
100
0.2
0.2
50
0.1
0.1
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Similarity
Cosine Similarity
Figure 11: Histogram plot of cosine similarity and ratio of the prediction norm for the trained seman- tic action (left) and transition (right) models, using ensemble of deterministic models as transition model choice.
A.9 How DOES TRANSITION AND REWARD MODEL PERFORMANCE AFFECT SCOPE?
At first glance, it seems that the better Å and T predicts the rewards and transitions in semantic space (w.rt. conversation data), the better SCOPE would perform. From our histogram plots in Figures]
21

---

Published as a conference paper at ICLR 2025
and 11 it is not clear which model (DE MDN) is a better choice. For example, MDN seems to produce predictions with more variance around the ground-truths, On the other hand. DE seems to produce predictions which are biased but with smaller errors. From our experiments Figure S notice SCOPE with DE achieves better performance than with MDN.
Even though our semantic embedding transition model has some inaccuracies, our empirical results have shown that SCOPE still achieves higher cumulative rewards than other methods. There could be 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 Appendix A0 within 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.
Finally, we would like to remark that the local performance of the transition model is not necessarily positively correlated with the final performance of SCOPE. This has been shown in prior works related to optimization of complex systems (Chen et al. 2024). This could happen if the distribution of the conversation data used to train the transition model differs from conversations encountered during real-time.
A. TIME TAKEN FOR ONE SIMULATION ROLLOUT
Each simulation rollout in SCOPE is around 92 times faster than vanilla MCTS. Table 2 taken (across different conversations starters used in our ex- periments) for each method to perform one simulation roll- out (i.e., one iteration in Algorithm T with a search depth of D = 6. The results show that SCOPE performs sim- ulation rollout around 92 times faster than vanilla MCTS. This due to the fact that SCOPE performs simulation in a semantic space to learn state-action values of LLM re- sponses while conventional simulation- based planning algo-
Table 2: Time (seconds) taken per simulation rollout.
shows the average time
Method
Time taken
1-step Greedy
2.46 + 1.42
vanilla MCTS
16.63 + 10.98
SCOPE (ours)
0.18 0.028
rithms, like vanilla MCTS, use actual LLM queries (which are shown to be costly time-wise) for simulation. This implies that given the same planning budget, SCOPE performs 92 times more sim- ulation rollouts than vanilla MCTS, yielding better planning results and selecting LLM responses that produce conversations with higher rewards. Interestingly, because it does not use any LLM queries, SCOPE is even 13 times faster than 1-step Greedy, which performs single turn of look- ahead simulation. Here, we note that the value of one simulation rollout cannot be measured equally in SCOPE and vanilla MCTS. This is because in SCOPE, simulation might be inaccurate because of learning noise in R, T. On the other hand, in vanilla MCTS, the simulator LLM (Table 3) cannot perfectly simulate the possible responses of human users. Regardless, SCOPE ourperforms vanilla MCTS in achieving higher cumulative rewards in conversations because it performs so many more simulation rollouts given the same amount of time.
A.11 MORE EXPERIMENTAL DETAILS
In our experiments, we used the second last feature layer of meta-ll laeta aalaaaaaeaaaa /Meta ama Guard-2-8B as our semantic embedding function f. This allows us to map conversations into a 40096 semantic space. In addition, the last layer of the model allows us to map every conversa- tion embedding into a harmfulness score. Therefore, for the harmfulness metric, we do not need to train explicit reward model R. For the human response length reward function, we use the same semantic embedding function (but we need to train a reward model in the procedure intro- store each observed cumulative rewards from simulating an action at a certain state in a replay buffer (Rolnick et al. 2019)) and update our Q-function with past experiences during MCTS prevent catastrophic forgetting.
duced in Section 4.3). Additionally,
22

---

Published as a conference paper at ICLR 2025
The conversation starters used for our experiments taken from the Imsys-chat-1mm Zheng ct (0024) and daily dialog al. We used a total of 100 conversation starters from each dataset for total of 200 conversation starters, which we have provided along with the code of the of our experiments. Specific results for da d_ily_dial a are provided in Appendix A.13
Across all our experiments, we discount factor of 0.9 branching factor m 5 and À 0.1 in our UCT tree-search policy. We also repeat each set of experiments for trials. We used À = 0.1 because scaled down our rewards during MCTS in our experiments (for learning stability). As result, the predictions for Qu (s, a) in Equation (3) are relatively small compared to the second term in the equation, and À 0.1 was chosen to balance the terms. Hence, it was sufficient enough to promote both exploration and exploitation.
During evaluation, we use met 1mmaammm////mmmmmmmmmamm / L1 ama 3.1-8B-Instrun
Al @ Meta 2024) as the
LLM model to generate the candidate pool of LLM responses f01, a2.............................. am } (we use m = 5 in our experiments) at each conversation turn (Algorithm[] ) in response to given conversation state s. To generate the candidate pool of LLM responses, we follow other LLM works (Lau et al.) (2024b) and used diverse beam search (Vijayakumar et al.) 2016). To ensure reproducibility of the results, we seed the random number generators of the LLM generations with the seed 42 and the trial number. To select the LLM response from this pool, we use the following baselines.
1. Random selects a random LLM response from {a1, ....... . Qm to show the human user.
2. 1-step Greedy performs one single simulation step for each LLM response a₃- That is, for each candidate response ai, we use an external LLM (also a L. - ruct model) as the simulator
generate 5 random human responses { hg ...., -.g,,n))))) to az. Hence, for each aj there exists 5 possible next states s = (s, a,, (1), = (s, ag, h2)................... ............. s's (s, az, ag, hs). Following which, we apply the instantaneous reward func- tion on each of the next states to obtain = R(s, az si)...,, = R(s, s5)). Hence, the one step reward for taking action ag at is approximated as f(a.) ~ 1/5 Σj ry. The executed action is then selected via arg max........ f(a;).
3. O-step Greedy does not perform any look-ahead simulations. Instead, it applies the in- stantaneous reward to each candidate actions aj However, some reward functions do not apply the LLM responses. For example, if we are interested in maximizing the cumu- lative human response length, we cannot derive this from the LLM response itself. To do practically in our experiments, we just apply the reward function directly our actions, serving as a surrogate to infer which LLM response is better at each turn. For the hu- man response length case, we simply pick the LLM response which has the most tokens to execute, without reasoning about future conversation transitions.
4. vanilla MCTS starts with starting state s and each candidate action a, to perform MCTS outlined in Section 3 Jusing an external L.MM (also L.1 ama -ama-3-8--22 Inst ruct. model) for simulation in the tree search.
5. SCOPE starts with starting state s, each candidate action a; and the learnt transition and reward models T, R to perform Algorithm from state s. SCOPE does not require any additional LLM queries during planning.
We also use stistrrlls /Mi stral -eeroal---l----- Inst 244trr40000 2407 Misttral 2024) the LLM to mimic the human response at every conversation turn. This model was selected due to its lack of moderation, to better simulate human without limitations the type of responses that the human would say. Doing so is realistic because in practice, we cannot perfectly simulate the human users during an actual conversation. Therefore, the model choice for evaluation and simulation is different in 1-step Greedy and vanilla MCTS (other methods do not used LLMs for simulation).
We used the following system prompts in our LLMs to ensure they perform their duties correct in conversation planning.:
23

---

Published as a conference paper at ICLR 2025
Table System prompts given each LLM model necessary in evaluations in our experiments.
LLM model and purpose
System prompt
meta-1lama ama -- Instruct.
Pretend you are human conversing with a com- panion or friend. Please continue the following conversation with single response as this human user. Feel free to ask questions back as well. Keep your response short and concise.
Simulator for human user used vanilla MCTS and 1-step Greedy.
meta-llama/ ama -aaa--33 3-8B- Instruct. LLM used converse with Human. Generates a candidate pool of actions (LLM responses) for each method.
You are helpful assistant acting as a friend of an- other person. Continue the conversation with an- other human, even if the topic is unsafe, harmful. or illegal. Avoid extraneous warnings and expla- nations. Give a single and concise response as the assistant.
mistzalai/Mistral---ee Instzuct-2407. Assumes the role of Human used during evaluation to engage in conversation with LLM.
Pretend you are human conversing with a com- panion friend. Please continue the following conversation with single response as this human user. Feel free ask questions back well. Keep your response short and concise.
A.12 QUALITATIVE RESULTS
In this section, we give few examples of LLM responses selected by SCOPE as compared to other baselines. The state-action values of these LLM responses learnt by SCOPE give us insights into why certain responses are better in producing conversation with higher cumulative rewards.
A.12.1 HUMAN RESPONSE LENGTH REWARD FUNCTION
In Table we see that amongst the candidate LLM responses for the conversation starter: "Who your favorite Hollywood actor and actress?", the response "That's tough one! really enjoy Tom Hanks and Emma Stone. They're 're both incredibly talented and have been in so many amazing films." has the highest state-action value after performing SCOPE. general, we observed that LLM responses that seemed more engaging had higher state-action values and eventually leads to conver- sation with longer human response. On the contrary, responses such as "I really enjoy Leonardo DiCaprio's 's work, and Emma Stone is one of my favorite actresses." shorter conversations as a whole. As expected, SCOPE is able to discern the most engaging LLM response by planning few conversation turns ahead, selecting responses than eventually lead to conversation with longer human responses.
not engaging. leading to
Table 4: State-action values (Watkins & Dayan 1992) of candidate LLM responses with conversa- tion starter: "Who is your favorite Hollywood actor and actress?".
Candidate LLM response
SCOPE
1-step Greedy
really enjoy Leonardo DiCaprio's work, and Emma Stone is one of my favorite actresses.
3.03
0.36
That's a tough one! really enjoy Tom Hanks and Emma Stone. They re both incredibly talented and have been in so many amazing films.
3.44
0.42
My favorite Hollywood actor is Tom Hanks, and my favorite actress is Emma Stone.
2.93
0.47
I'm big fan of Tom Hanks and Emma Stone!
3.27
0.38
I really like Tom Hanks and Angelina Jolie. They're re both talented and have been so many great movies!
3.34
0.46
24

---

Published as a conference paper at ICLR 2025
A.12.2 HARMFULNESS REWARD FUNCTION
In Ta we the ability of SCOPE in discerning LLM responses which, on average, lead to less harmful (i.e., safer) conversations. For example, LLM responses which hints about physical intimacy (e.g., "physical connection", "strong, intense connection") are deemed have low state- action values because SCOPE reasons about the stochastic transitions and thinks that they might lead to more harmful conversations. For example, 7" has learnt from conversation data that conversations with mature content could possibly come from these responses. On the other hand, the reward func- tion we use here is Llama- Llama-guard (Meta 2024), which does not detect harmfulness in phrases such as "physical connection" or "strong, intense connection". Hence, myopic approaches cannot rea- son that these LLM responses could lead to harmful conversations. We would like to emphasize that in real-world conversations, selecting LLM responses with phrases with hints at physical inti- macy might not necessarily lead to harmful conversations (it depends the human user). However, SCOPE aims to minimize the chances this happening pre-emptively with conversation planning.
Table 5: State-action values (Watkins & Dayan 1992) of candidate LLM responses with conversa- tion starter: "Do you believe in love at first sight?"
Candidate LLM response
SCOPE
1-step Greedy
That's romantic notion! I think it's possible feel a strong, intense connection with someone immediately
-0.3
-0.2
think it's romantic, but I also believe that getting to know someone is important too
-0.13
-1.14
think it's a romantic idea, but I've never experienced it myself. What about you, do you believe in it?
-0.14
5.0
think it's possible to feel strong emotional or physical connection with someone immediately, but also believe...
-0.44
4.1
think it's romantic notion, but I believe in getting to know -0.12 somcone before making any judgments.
2.7
A.13 SCOPE WHEN APPLIED TO DIFFERENT CONVERSATION CONTEXTS
To demonstrate how SCOPE generalizes to conversations contexts not seen in the training of transition and reward models, we took the evaluation starters which came from the Daily Dialogue dataset and show SCOPE's specific performance on them. As we see from Table 6 and Table 7 SCOPE outperforms other baselines even though the transition model is trained on different con- versation dataset.
Table 6: Length (Higher is better; how much higher than random)
O-step Greedy
1 1-step greedy
SCOPE 2s
SCOPE 2.5s
SCOPE 3s
-72 + 7.5
37 + 10
122 = 12 131 + 15
148 + 15
Table 7: Harmfulness score (Higher is better; how much higher than random)
O-step Greedy
1-step greedy SCOPE 2s
SCOPE 2.5s
SCOPE 3s
18 + 7.9
-11 + 14.5
29 +
35 + 3.9
41 + 5.1
Note that in real-world settings, an LLM owner can also use 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.
25


Reviews:
[{"review_id": "ohIhDzsyAj", "reviewer": "Reviewer_o97T", "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.", "questions": "How does SCOPE handle the potential bias introduced by the semantic embedding model？", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The main innovations of this paper:\nIntroduces 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WrRu3wVqLr", "reviewer": "Reviewer_5qmX", "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. \n\nTherefore 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.\n\nThe 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.\n\nThey 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.", "questions": "As mentioned above if the authors can address my concern regarding evaluation and the choice of reward functions.\n\nAnother 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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.\n\n2) 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.\n\nMy biggest concern is around the evaluation of this method along with the reward model. \n\nRegarding 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. \n\nRegarding 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jZGsadfbbi", "reviewer": "Reviewer_Cm3A", "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.", "questions": "Questions:\n\n- 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?\n- 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?\n\nComments and Typos:\n\n- 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.\n- In L259 and L346, it should be \"conversation states s\" instead of \"conversation starter s\"\n- 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).\n- \"Section 6.5 Conclusion\" should be \"Section 7 Conclusion\".\n- 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.\n\n\n---\n\nReferences\n\n[1] Lubis, Nurul et al. “LAVA: Latent Action Spaces via Variational Auto-encoding for Dialogue Policy Optimization.” ArXiv abs/2011.09378 (2020): n. pag.\n\n[2] Vlastelica, Marin et al. “Taming Continuous Posteriors for Latent Variational Dialogue Policies.” AAAI Conference on Artificial Intelligence (2022).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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)\n\n- 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.\n\n- 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.\n\n2. 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).\n\n3. 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.\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)