Exact Frontier Coupling for Adaptive Language Model Policy Evaluation

Independent evaluation of adaptive language-model agents often repeats identical model requests across policies. We introduce Exact Frontier Coupling (EFC), a joint evaluator that shares these requests while preserving each policy's standalone trajectory distribution. At a history shared by active policies, EFC groups identical conditional action distributions and solves a local multi-marginal optimal transport problem to minimize expected distinct-request cost. We prove marginal trajectory preservation under matched response kernels. On 1,200 constructed frontiers, EFC reduces expected weighted request cost by 1.65% relative to common-quantile coupling optimized over every action order. In paired evaluations of the same 52 BFCL tasks across four models, exact-request sharing reduces physical model calls by 29-44% and yields 1.66-1.82$\times$ warmed-worker speedups over independent execution, with identical observed trajectories and official outcomes. The resulting savings make it feasible to evaluate more adaptive agents across more tasks under the same inference budget.