一句话：提出带分支定界半环的二元决策图IR，将概率优化编译为可扩展的推断与优化流程。
概率推断本身很难，在其上做优化更难。论文提出一种“通过编译进行优化”的策略：引入以分支定界半环加权的二元决策图作为中间表示（IR）。该 IR 能依据程序结构自动分解问题，并用直接的分支定界算法剪除次优值以寻找最优解；它还天然支持分阶段编译，使程序员可在编译中途查询最优值来指导程序后续执行。作者用同一 IR 实现了两门语言：函数式语言 dappl 求解最大期望效用，支持一等奖励、决策与条件化；命令式语言 pineappl 执行精确概率推断，并通过 staging 支持嵌套边际最大后验（MMAP）优化，展示了该 IR 的有效性与灵活性。
Probabilistic inference is fundamentally hard, yet many tasks require optimization on top of inference, which is even harder. We present a new optimization-via-compilation strategy to scalably solve a certain class of such problems. In particular, we introduce a new intermediate representation (IR), binary decision diagrams weighted by a novel notion of branch-and-bound semiring, that enables a scalable branch-and-bound based optimization procedure. This IR automatically factorizes problems through program structure and prunes suboptimal values via a straightforward branch-and-bound style algorithm to find optima. Additionally, the IR is naturally amenable to staged compilation, allowing the programmer to query for optima mid-compilation to inform further executions of the program. We showcase the effectiveness and flexibility of the IR by implementing two performant languages that both compile to it: dappl and pineappl . dappl is a functional language that solves maximum expected utility problems with first-class support for rewards, decision making, and conditioning. pineappl is an imperative language that performs exact probabilistic inference with support for nested marginal maximum a posteriori (MMAP) optimization via staging.
@article{paperbot3187,
title = {Scaling Optimization over Uncertainty via Compilation},
author = {Minsung Cho and John Gouwar and Steven Holtzen},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA1},
year = {2025},
doi = {10.1145/3720500}
}