verifier-guided-decoding

%23%20%2F%2F%2F%20script%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.4.3%22%2C%0A%23%20%20%20%20%20%22matplotlib%3D%3D3.10.1%22%2C%0A%23%20%5D%0A%23%20requires-python%20%3D%20%22%3E%3D3.12%22%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%0A%20%20%20%20return%20np%2C%20plt%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Best-of-%24N%24%20%2B%20Verifier-Guided%20Decoding%0A%0A%20%20%20%20A%20tiny%20language%20model%20(LM)%20can%20solve%20simple%20Python%20coding%20tasks%20if%20it%20generates%20enough%0A%20%20%20%20samples%2C%20but%20raw%20temperature%20sampling%20wastes%20budget%20on%20syntax%20errors%20and%20off-task%20outputs.%0A%20%20%20%20These%20two%20strategies%20are%20not%20equivalent%3A%0A%0A%20%20%20%20-%20**Baseline**%3A%20generate%20%24N%24%20samples%3B%20take%20the%20first%20valid%20completion%20from%20a%20hidden%20test.%0A%20%20%20%20-%20**Verifier-guided**%3A%20after%20each%20generation%2C%20a%20tiny%20verifier%20*accepts*%20or%20*rejects*%20it.%0A%20%20%20%20%20%20Rejecting%20triggers%20backtrack%20%2B%20regenerate%2C%20at%20extra%20cost.%0A%0A%20%20%20%20Because%20backtrack%20redo%20means%20the%20model%20generates%20more%20tokens%20for%20fewer%20valid%20completions%2C%0A%20%20%20%20the%20measure%20of%20interest%20is%20**expected%20total%20generation%20tokens%20per%20successful%20sample**%2C%20not%0A%20%20%20%20simple%20valid%20rate.%0A%0A%20%20%20%20This%20notebook%20models%20both%20strategies%20and%20gives%20you%20a%20compact%20tool%20to%20explore%20regimes%20where%0A%20%20%20%20a%20verifier%20pays%20for%20itself.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Notation%0A%0A%20%20%20%20-%20%24p_s%24%3A%20probability%20a%20single%20sample%20passes%20the%20hidden%20unit%20test.%0A%20%20%20%20-%20%24p_v%24%3A%20precision%20of%20the%20verifier%20(probability%20it%20*accepts*%20passing%20samples).%0A%20%20%20%20-%20%24N%24%3A%20generation%20budget%20(max%20samples%20per%20attempt).%0A%20%20%20%20-%20%24V%24%3A%20verifier%20inference%20cost%20per%20sample%20(relative%20to%20one%20generate).%0A%20%20%20%20-%20%24C(p_s%2C%20p_v%2C%20N)%24%3A%20expected%20generation-token%20cost%20to%20produce%20one%20passing%20sample.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20_compute_cost(p_s%2C%20p_v%2C%20N%2C%20generator_cost%3D1.0%2C%20verifier_cost%3D0.35)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Expected%20generation-token%20cost%20for%20one%20successful%20sample.%22%22%22%0A%20%20%20%20%20%20%20%20if%20p_s%20%3C%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20float(%22inf%22)%0A%20%20%20%20%20%20%20%20expected_samples%20%3D%201.0%20%2F%20(p_s%20%2B%201e-12)%0A%20%20%20%20%20%20%20%20if%20p_v%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20expected_cost%20%3D%20generator_cost%20*%20expected_samples%0A%20%20%20%20%20%20%20%20%20%20%20%20expected_cost%20%2B%3D%20verifier_cost%20*%20(expected_samples%20-%201.0)%20*%20(1.0%20-%20p_v)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20expected_cost%20%3D%20generator_cost%20*%20expected_samples%0A%20%20%20%20%20%20%20%20return%20float(expected_cost)%0A%0A%20%20%20%20def%20_expected_successes(p_s%2C%20p_v%2C%20N)%3A%0A%20%20%20%20%20%20%20%20_S%20%3D%20np.arange(1%2C%20N%20%2B%201)%0A%20%20%20%20%20%20%20%20_base_prob%20%3D%201.0%20-%20(1.0%20-%20p_s)%20**%20_S%0A%20%20%20%20%20%20%20%20_verif_prob%20%3D%201.0%20-%20(1.0%20-%20p_s%20*%20p_v)%20**%20_S%0A%20%20%20%20%20%20%20%20return%20_S%2C%20_base_prob%2C%20_verif_prob%0A%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20slider_p_s%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.05%2C%0A%20%20%20%20%20%20%20%20stop%3D0.95%2C%0A%20%20%20%20%20%20%20%20step%3D0.05%2C%0A%20%20%20%20%20%20%20%20value%3D0.25%2C%0A%20%20%20%20%20%20%20%20label%3D%22Pass%20probability%20p_s%20(single%20sample)%22%2C%0A%20%20%20%20)%0A%20%20%20%20slider_p_v%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.5%2C%0A%20%20%20%20%20%20%20%20stop%3D1.0%2C%0A%20%20%20%20%20%20%20%20step%3D0.01%2C%0A%20%20%20%20%20%20%20%20value%3D0.88%2C%0A%20%20%20%20%20%20%20%20label%3D%22Verifier%20precision%20p_v%22%2C%0A%20%20%20%20)%0A%20%20%20%20slider_N%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1%2C%0A%20%20%20%20%20%20%20%20stop%3D64%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20value%3D16%2C%0A%20%20%20%20%20%20%20%20label%3D%22Generation%20budget%20N%22%2C%0A%20%20%20%20)%0A%20%20%20%20slider_p_s%2C%20slider_p_v%2C%20slider_N%0A%20%20%20%20return%20slider_N%2C%20slider_p_s%2C%20slider_p_v%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%23%20Sampling%20knobs%0A%20%20%20%20Adjust%20the%20pass%20rate%2C%20verifier%20precision%2C%20and%20budget.%20Decisions%20here%20should%20reflect%20validator%20precision%20curves%20for%20the%20target%20model%20family.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(slider_N%2C%20slider_p_s%2C%20slider_p_v)%3A%0A%20%20%20%20p_s%20%3D%20float(slider_p_s.value)%0A%20%20%20%20p_v%20%3D%20float(slider_p_v.value)%0A%20%20%20%20N%20%3D%20int(slider_N.value)%0A%20%20%20%20_baseline_cost%20%3D%20_compute_cost(p_s%2C%200.0%2C%20N)%0A%20%20%20%20_verifier_cost%20%3D%20_compute_cost(p_s%2C%20p_v%2C%20N)%0A%20%20%20%20_successes%20%3D%20_expected_successes(p_s%2C%20p_v%2C%20N)%0A%20%20%20%20_plot_curves(p_s%2C%20p_v%2C%20N%2C%20_baseline_cost%2C%20_verifier_cost%2C%20_successes)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_plot_curves(np%2C%20plt%2C%20slider_N%2C%20slider_p_s%2C%20slider_p_v)%3A%0A%20%20%20%20def%20_plot_curves(p_s%2C%20p_v%2C%20N%2C%20baseline_cost%2C%20verifier_cost%2C%20successes)%3A%0A%20%20%20%20%20%20%20%20fig%2C%20axes%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(12%2C%204))%0A%20%20%20%20%20%20%20%20S%2C%20base_prob%2C%20verif_prob%20%3D%20successes%0A%0A%20%20%20%20%20%20%20%20%23%20Left%3A%20success%20accumulation%0A%20%20%20%20%20%20%20%20ax%20%3D%20axes%5B0%5D%0A%20%20%20%20%20%20%20%20ax.step(S%2C%20base_prob%2C%20where%3D%22mid%22%2C%20label%3D%22Baseline%22)%0A%20%20%20%20%20%20%20%20ax.step(S%2C%20verif_prob%2C%20where%3D%22mid%22%2C%20label%3D%22Verifier-guided%22)%0A%20%20%20%20%20%20%20%20ax.set_xlabel(%22Budget%20N%22)%0A%20%20%20%20%20%20%20%20ax.set_ylabel(%22Cumulative%20success%20probability%22)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22Success%20accumulation%20at%20p_s%3D%7Bp_s%3A.2f%7D%2C%20p_v%3D%7Bp_v%3A.2f%7D%22)%0A%20%20%20%20%20%20%20%20ax.legend(loc%3D%22lower%20right%22)%0A%20%20%20%20%20%20%20%20ax.grid(True%2C%20alpha%3D0.2)%0A%0A%20%20%20%20%20%20%20%20%23%20Right%3A%20expected%20cost%20vs%20p_s%20curve%0A%20%20%20%20%20%20%20%20ax%20%3D%20axes%5B1%5D%0A%20%20%20%20%20%20%20%20p_s_grid%20%3D%20np.linspace(0.05%2C%200.95%2C%2060)%0A%20%20%20%20%20%20%20%20base_costs%20%3D%20%5B_compute_cost(p%2C%200.0%2C%20N)%20for%20p%20in%20p_s_grid%5D%0A%20%20%20%20%20%20%20%20verif_costs%20%3D%20%5B_compute_cost(p%2C%20p_v%2C%20N)%20for%20p%20in%20p_s_grid%5D%0A%20%20%20%20%20%20%20%20ax.plot(p_s_grid%2C%20base_costs%2C%20label%3D%22Baseline%22)%0A%20%20%20%20%20%20%20%20ax.plot(p_s_grid%2C%20verif_costs%2C%20label%3D%22Verifier-guided%22)%0A%20%20%20%20%20%20%20%20ax.axvline(p_s%2C%20color%3D%22red%22%2C%20linestyle%3D%22--%22%2C%20alpha%3D0.5%2C%20label%3D%22Selected%20p_s%22)%0A%20%20%20%20%20%20%20%20ax.set_xlabel(%22Pass%20probability%20p_s%22)%0A%20%20%20%20%20%20%20%20ax.set_ylabel(%22Expected%20relative%20cost%22)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22Expected%20cost%20per%20successful%20sample%20at%20N%3D%7BN%7D%22)%0A%20%20%20%20%20%20%20%20ax.legend(loc%3D%22upper%20right%22)%0A%20%20%20%20%20%20%20%20ax.grid(True%2C%20alpha%3D0.2)%0A%20%20%20%20%20%20%20%20fig.tight_layout()%0A%20%20%20%20%20%20%20%20return%20fig%0A%0A%20%20%20%20_plot_curves(%0A%20%20%20%20%20%20%20%20float(slider_p_s.value)%2C%0A%20%20%20%20%20%20%20%20float(slider_p_v.value)%2C%0A%20%20%20%20%20%20%20%20int(slider_N.value)%2C%0A%20%20%20%20%20%20%20%20_compute_cost(float(slider_p_s.value)%2C%200.0%2C%20int(slider_N.value))%2C%0A%20%20%20%20%20%20%20%20_compute_cost(%0A%20%20%20%20%20%20%20%20%20%20%20%20float(slider_p_s.value)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20float(slider_p_v.value)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20int(slider_N.value)%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20_expected_successes(%0A%20%20%20%20%20%20%20%20%20%20%20%20float(slider_p_s.value)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20float(slider_p_v.value)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20int(slider_N.value)%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20slider_N%2C%20slider_p_s%2C%20slider_p_v)%3A%0A%20%20%20%20p_s%20%3D%20float(slider_p_s.value)%0A%20%20%20%20p_v%20%3D%20float(slider_p_v.value)%0A%20%20%20%20N%20%3D%20int(slider_N.value)%0A%20%20%20%20_%2C%20_%2C%20base_success%20%3D%20_expected_successes(p_s%2C%200.0%2C%20N)%0A%20%20%20%20_%2C%20_%2C%20verif_success%20%3D%20_expected_successes(p_s%2C%20p_v%2C%20N)%0A%20%20%20%20baseline_cost%20%3D%20_compute_cost(p_s%2C%200.0%2C%20N)%0A%20%20%20%20verifier_cost%20%3D%20_compute_cost(p_s%2C%20p_v%2C%20N)%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22**Selected**%3A%20%24p_s%20%3D%20%7Bp_s%3A.2f%7D%24%2C%20%24p_v%20%3D%20%7Bp_v%3A.2f%7D%24%2C%20%24N%20%3D%20%7BN%7D%24%20%20%5Cn%22%0A%20%20%20%20%20%20%20%20f%22Baseline%20success%20at%20%24N%3D%7BN%7D%24%3A%20%7Bbase_success%5B-1%5D%3A.2%25%7D%20%20%5Cn%22%0A%20%20%20%20%20%20%20%20f%22Verifier%20success%20at%20%24N%3D%7BN%7D%24%3A%20%7Bverif_success%5B-1%5D%3A.2%25%7D%20%20%5Cn%22%0A%20%20%20%20%20%20%20%20f%22Expected%20cost%20ratio%20verifier%20%2F%20baseline%3A%20%7Bverifier_cost%20%2F%20baseline_cost%20if%20baseline_cost%20%3E%200%20else%20float('inf')%3A.2f%7D%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aapp._unparsable_cell(%0A%20%20%20%20%22%22%22%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%5C%22%5C%22%5C%22%0A%20%20%20%20%20%20%20%20%23%23%20Model%20risk%20layers%0A%0A%20%20%20%20%20%20%20%201.%20**Backtrack%20latency**%3A%20decoding%20backtrack%20adds%20runtime%20cost%2C%20but%20the%20headline%20claim%20is%20about%20quality%20gains%2C%20not%20latency%20reductions.%0A%20%20%20%20%20%20%20%202.%20**Verifier%20VRAM**%3A%20roughly%20the%20size%20of%20the%20base%20model%2C%20doubling%20VRAM%20and%20memory%20bandwidth.%0A%20%20%20%20%20%20%20%203.%20**Fitting%20risk**%3A%20real%20verifier%20precision%20%24p_v%24%20for%200.5B%20models%20is%20likely%20volatile%20across%20task%20families%20(coding%20vs%20chat%20vs%20tool%20use).%0A%0A%20%20%20%20%20%20%20%20%23%23%20Operational%20implication%0A%0A%20%20%20%20%20%20%20%20Store%20verifier%20precision%20for%20each%20model%20family%20rather%20than%20treating%20it%20as%20universal.%0A%20%20%20%20%20%20%20%20Re-tune%20%24p_s%24%2C%20%24p_v%24%2C%20and%20%24N%24%20when%20moving%20between%20Gemma4-QAT%2C%20DeepSeek%20V4%20Flash%2C%20Qwen3.6%2C%0A%20%20%20%20%20%20%20%20and%20other%20candidate%20runtimes.%0A%20%20%20%20%20%20%20%20%5C%22%5C%22%5C%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%20%20%20%20app%20%3D%20app%0A%20%20%20%20%22%22%22%2C%0A%20%20%20%20name%3D%22_%22%0A)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A