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., safety alignment, engagement) of a conversation is important and can only be exactly knownat the end of the conversation. To maximize this expected alignment quality,conversation planning reasons about the stochastic transitions within a conversation to select the optimal LLM response at each turn. Existing simulation-basedconversation 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 forreal-time conversations. This paper presents a novel approach called Semanticspace COnversation Planning with improved Efficiency (SCOPE) that exploits thedense semantic representation of conversations to perform conversation planningefficiently. In particular, SCOPE models the stochastic transitions in conversationsemantics and their associated rewards to plan entirely within the semantic space.By doing so, SCOPE selects the optimal LLM response at every conversation turnwithout needing additional LLM queries for simulation. As a result, SCOPE canperform conversation planning 70 times faster than conventional simulation-basedplanning algorithms when applied to a wide variety of conversation starters andtwo reward functions seen in the real world, yet achieving a higher reward withina practical planning budget.