A voice-based agent service provides one or more voice agents to respond to voice-based requests. For example, when a question is recieved by the voice-based agent service it can be matched to a voice-ready knowledge base. The voice-ready knowledge base is obtained offline and organized as nodes in a conversation graph. The question can be matched to a node and then subsequent nodes can be predicted by a conversation model based on previously traveresed nodes and further input in realtime.