cs.LGNov 8, 2026

How Efficient Is Your Agent? Online Predictive Bounds under Budget Constraints

Authors: Roy Maor Lotan, Shai Feldman, Yaniv Romano

Organizations: Department of Electrical and Computer Engineering, Technion, Israel · Department of Computer Science, Technion, Israel

Abstract

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 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.

Figures & tables

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. BAGEN: Are LLM Agents Budget-Aware?

    May 29, 2026Yuxiang Lin, Zihan Wang, Mengyang Liu +9LLM Agent EvaluationAI Agent Benchmarks

  2. When and What to Teach: Budget-Aware Online Adaptation for Web Agents

    Aug 31, 2026Jianwei Zhang, Sihan Cao, Pengcheng Zheng +7Online Knowledge DistillationLLM Agent Training