Uncertainty quantification (UQ) is essential for safe deployment of generative AI models such as large language models (LLMs), especially in high-stakes applications. Conformal prediction (CP) offers a principled UQ framework, but classical methods focus on regression and classification, relying on geometric distances or softmax scores—tools that presuppose structured outputs. We depart from this paradigm by studying CP in a query-only setting, where prediction sets must be constructed solely from finite queries to a black-box generative model, introducing a new trade-off between coverage, test-time query budget, and informativeness. We introduce Conformal Prediction with Query Oracle (CPQ), a framework characterizing the optimal interplay between these objectives. Our finite-sample algorithm is grounded in two principles: the first characterizes the optimal query policy, and the second the optimal mapping from queried samples to prediction sets, remarkably connecting both to the classical missing mass problem in statistics. Fine-grained experiments on three real-world open-ended tasks and two LLMs, show CPQ's applicability to any black-box LLM and highlight: (1) individual contribution of each principle to CPQ’s performance, and (2) CPQ's ability to yield significantly more informative prediction sets than existing conformal methods for language UQ.