Action-Objective Regret for Fixed-Action Adaptive Inference

This is a preprint. It has not been peer reviewed. Adaptive inference systems spend different amounts of computation on different inputs, but the rule that allocates this computation is usually learned or calibrated from imperfect signals. This paper studies the deployment risk of that allocation rule after a set of compute actions has been fixed. For each action a, we write the conditional action objective as qa(x) = ra(x)+λca(x), combining predictive loss and inference cost, and view adaptive inference as choosing the action with the smallest estimated objective. Within this fixed-action abstraction, the central organizing result is an oracle-regret bound for plug-in compute allocation. If the estimated action objectives are uniformly within η of the true objectives, the selected policy has at most 2η excess cost-augmented risk; this constant is worst-case sharp. A margin-localized refinement, including a finite-sample binned version, shows that allocation errors matter only near action-tie boundaries, yielding faster rates when such near-ties are rare. This makes difficulty calibration an action-ordering problem rather than a generic claim that cost regularization is new. We then instantiate finite-sample calibration guarantees for finite policy classes, binned difficulty policies, Monte Carlo action evaluation, ordinary logged feedback, and nested sequential logs in which deeper computation reveals prefix-action outcomes. Lower bounds show that weak logged overlap can be an information barrier, not just an artifact of IPS analysis, and that terminal-only logs can be parametrically less informative than nested prefix logs from the same runs. The same action-value view yields a Lagrangian interpretation of average compute budgets, a marginal-utility stopping rule for ordered computation, and simple ceilings for verifier-guided and latent-difficulty resampling. Reproducible synthetic, text-classifier routing, and handwritten-digits checks instantiate the assumptions and illustrate the predicted failure modes; they are CPU-scale sanity checks for the theory, not large-scale LLM routing benchmarks.