How Efficient Is Your Agent? Online Predictive Bounds under Budget Constraints
En palabras de los autores
We evaluate AI agents in an online setting where tasks arrive sequentially and, before running each task, we construct an upper predictive bound on its time-to-success---the number of interactions until the task is completed successfully. Under a limited budget, some runs are stopped early, so their time-to-success is unobserved (right-censored), and the correctness of the bound may be unknown. We introduce \emph{PRedictive Bounds for Online Budget Efficiency} (PROBE), a method for constructing calibrated upper predictive bounds while adaptively allocating a limited budget across agent tasks to reduce the anticipated coverage deficit. Our method calibrates the bounds online using inverse-probability-weighted feedback together with a correction designed to minimize coverage deficit while remaining unbiased. We prove that PROBE provides a coverage guarantee for any finite time horizon while satisfying the budget constraint. Experiments on software engineering, retrieval-augmented generation, and instruction following show that PROBE attains a coverage rate closer to the target level with tighter predictive bounds than a calibrated baseline.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.