@inproceedings{nikita-etal-2026-brave,
title = "{BRAVE}: Budget-Aware Reflective {A}uto{P}rompting for Efficient Evolutionary Prompt Optimization",
author = "Nikita, Kulin and
Viktor, Zhuravlev and
Artur, Khairullin and
Muravyov, Sergey and
Makarov, Ilya and
Sukhorukov, Daniil",
editor = {Aziz, Wilker and
Berant, Jonathan and
Eikema, Bryan and
Ilia, Evgenia and
de Marneffe, Marie-Catherine and
Plank, Barbara and
Shelmanov, Artem and
Swayamdipta, Swabha and
Tiedemann, J{\"o}rg and
Vazhentsev, Artem and
V{\'a}zquez, Ra{\'u}l and
Zerva, Chrysoula},
booktitle = "The Proceedings of the Third Workshop on Uncertainty-Aware {NLP}",
month = oct,
year = "2026",
address = "Budapest, Hungary",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.uncertainlp-main.36/",
pages = "590--617",
ISBN = "979-8-89176-486-6",
abstract = "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."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="nikita-etal-2026-brave">
<titleInfo>
<title>BRAVE: Budget-Aware Reflective AutoPrompting for Efficient Evolutionary Prompt Optimization</title>
</titleInfo>
<name type="personal">
<namePart type="given">Kulin</namePart>
<namePart type="family">Nikita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Zhuravlev</namePart>
<namePart type="family">Viktor</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Khairullin</namePart>
<namePart type="family">Artur</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Sergey</namePart>
<namePart type="family">Muravyov</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ilya</namePart>
<namePart type="family">Makarov</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Daniil</namePart>
<namePart type="family">Sukhorukov</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-10</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>The Proceedings of the Third Workshop on Uncertainty-Aware NLP</title>
</titleInfo>
<name type="personal">
<namePart type="given">Wilker</namePart>
<namePart type="family">Aziz</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jonathan</namePart>
<namePart type="family">Berant</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bryan</namePart>
<namePart type="family">Eikema</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Evgenia</namePart>
<namePart type="family">Ilia</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Marie-Catherine</namePart>
<namePart type="family">de Marneffe</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Barbara</namePart>
<namePart type="family">Plank</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Artem</namePart>
<namePart type="family">Shelmanov</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Swabha</namePart>
<namePart type="family">Swayamdipta</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jörg</namePart>
<namePart type="family">Tiedemann</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Artem</namePart>
<namePart type="family">Vazhentsev</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Raúl</namePart>
<namePart type="family">Vázquez</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Chrysoula</namePart>
<namePart type="family">Zerva</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Budapest, Hungary</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-486-6</identifier>
</relatedItem>
<abstract>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.</abstract>
<identifier type="citekey">nikita-etal-2026-brave</identifier>
<location>
<url>https://aclanthology.org/2026.uncertainlp-main.36/</url>
</location>
<part>
<date>2026-10</date>
<extent unit="page">
<start>590</start>
<end>617</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T BRAVE: Budget-Aware Reflective AutoPrompting for Efficient Evolutionary Prompt Optimization
%A Nikita, Kulin
%A Viktor, Zhuravlev
%A Artur, Khairullin
%A Muravyov, Sergey
%A Makarov, Ilya
%A Sukhorukov, Daniil
%Y Aziz, Wilker
%Y Berant, Jonathan
%Y Eikema, Bryan
%Y Ilia, Evgenia
%Y de Marneffe, Marie-Catherine
%Y Plank, Barbara
%Y Shelmanov, Artem
%Y Swayamdipta, Swabha
%Y Tiedemann, Jörg
%Y Vazhentsev, Artem
%Y Vázquez, Raúl
%Y Zerva, Chrysoula
%S The Proceedings of the Third Workshop on Uncertainty-Aware NLP
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-486-6
%F nikita-etal-2026-brave
%X 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.
%U https://aclanthology.org/2026.uncertainlp-main.36/
%P 590-617
Markdown (Informal)
[BRAVE: Budget-Aware Reflective AutoPrompting for Efficient Evolutionary Prompt Optimization](https://aclanthology.org/2026.uncertainlp-main.36/) (Nikita et al., UncertaiNLP 2026)
ACL