Theoretical guarantees on the best-of-n alignment policy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913864569847808 |
|---|---|
| author | Beirami, Ahmad Agarwal, Alekh Berant, Jonathan D'Amour, Alexander Eisenstein, Jacob Nagpal, Chirag Suresh, Ananda Theertha |
| author_facet | Beirami, Ahmad Agarwal, Alekh Berant, Jonathan D'Amour, Alexander Eisenstein, Jacob Nagpal, Chirag Suresh, Ananda Theertha |
| contents | A simple and effective method for the inference-time alignment and scaling test-time compute of generative models is best-of-$n$ sampling, where $n$ samples are drawn from a reference policy, ranked based on a reward function, and the highest ranking one is selected. A commonly used analytical expression in the literature claims that the KL divergence between the best-of-$n$ policy and the reference policy is equal to $\log (n) - (n-1)/n.$ We disprove the validity of this claim, and show that it is an upper bound on the actual KL divergence. We also explore the tightness of this upper bound in different regimes, and propose a new estimator for the KL divergence and empirically show that it provides a tight approximation. We also show that the win rate of the best-of-$n$ policy against the reference policy is upper bounded by $n/(n+1)$ and derive bounds on the tightness of this characterization. We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-$n$ alignment policy, which demonstrate that very good tradeoffs are achievable with $n < 1000$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_01879 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Theoretical guarantees on the best-of-n alignment policy Beirami, Ahmad Agarwal, Alekh Berant, Jonathan D'Amour, Alexander Eisenstein, Jacob Nagpal, Chirag Suresh, Ananda Theertha Machine Learning Computation and Language Information Theory A simple and effective method for the inference-time alignment and scaling test-time compute of generative models is best-of-$n$ sampling, where $n$ samples are drawn from a reference policy, ranked based on a reward function, and the highest ranking one is selected. A commonly used analytical expression in the literature claims that the KL divergence between the best-of-$n$ policy and the reference policy is equal to $\log (n) - (n-1)/n.$ We disprove the validity of this claim, and show that it is an upper bound on the actual KL divergence. We also explore the tightness of this upper bound in different regimes, and propose a new estimator for the KL divergence and empirically show that it provides a tight approximation. We also show that the win rate of the best-of-$n$ policy against the reference policy is upper bounded by $n/(n+1)$ and derive bounds on the tightness of this characterization. We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-$n$ alignment policy, which demonstrate that very good tradeoffs are achievable with $n < 1000$. |
| title | Theoretical guarantees on the best-of-n alignment policy |
| topic | Machine Learning Computation and Language Information Theory |
| url | https://arxiv.org/abs/2401.01879 |