Automatic prompt optimization is an uncertain sequential decision problem: an editing operator’s quality gain and context-dependent token cost are unknown before execution. We introduce BRAVE (Budget-Aware Reflective AutoPrompting for Efficient Evolutionary Prompt Optimization), a population-based optimizer that treats this operational uncertainty as a control signal. Its EVC Controller maintains per-operator Bayesian models of quality gain, token cost, and improvement probability, then selects among eleven generation and mutation operators by uncertainty-penalized predicted utility per token under a predicted-cost feasibility guard. An EMA return-on-investment mechanism revises this decision process from realized outcomes, while diversity management preserves alternative prompt hypotheses. On seven datasets, BRAVE outperforms EvoPrompt, PromptBreeder, and GEPA on 7/7 tasks; its advantage over the strongest external baseline ranges from 0.002 to 0.150 absolute score points. Under 20k, 40k, and 80k nominal budgets, BRAVE respectively achieves average quality 0.779, 0.807, and 0.812 versus GEPA’s 0.771, 0.775, and 0.781, while using 21.4k, 41.0k, and 72.4k tokens versus 46.1k, 65.2k, and 96.5k. BRAVE therefore formulates reliable prompt optimization as uncertainty-aware resource allocation: uncertainty about an edit’s value and cost directly changes the action selected.