Anytime Contracts for AI Services

1 INTRODUCTION

• Fixed-duration contracts can fail under user-controlled stopping: ending after a failure can leave an all-success contract unpaid, while stopping after success can make a per-success contract favor cheaper models.These examples motivate contracts that account for unknown exit rules.Source: §1 · p. 2
• The paper formalizes stopping-time uncertainty as a Principal-Agent game requiring high-effort incentives to hold uniformly over admissible, possibly data-dependent user stopping rules.This is a strict generalization of fixed-duration contract design, which corresponds to a singleton class of stopping rules.Source: §1 · p. 2
• Budget-optimal anytime contracts are scaled sequential likelihood-ratio tests, with required budgets increasing when the target policy is costlier or harder to distinguish.For bounded stopping-time families, contracts can be computed by reducing the problem to optimal stopping.Source: §1 · p. 2
• An e-value construction approximates the optimal contract using observed signals alone, provides anytime service-level guarantees, and can sometimes recover the optimum exactly.The optimal construction requires knowledge of output distributions induced by provider routing policies.Source: §1 · p. 2
• Experiments use synthetic data and closed-source LLM data to examine stopping-time effects, robustness costs, partial distributional information, and deterrence of alternative policies.The LLM experiments use the Holistic Agent Leaderboard [18].Source: §1 · p. 2

1.1 Related Work

• The work extends research on delegated AI moral hazard and statistical contracts beyond fixed-duration interactions, and differs from work where the agent strategically chooses stopping criteria.It studies hidden provider actions with adversarial stopping rules, rather than adverse selection or agent-chosen stopping criteria.Source: §1.1 · pp. 2–3

2 PROBLEM SETTING

• At each discrete step, the client sends prompts and receives responses, and interaction may end after any step based on observed output quality.A step can represent a query, a monthly batch, or another potentially irregular unit of observation.Source: §2 · p. 3
• The design goal is an anytime payment scheme that incentivizes high effort despite termination rules that may depend on observed history.The setting allows data-dependent stopping rules from an admissible class.Source: §2 · p. 3
• The provider routes prompts among generative models, potentially at random and adaptively, while the client observes prompt-response pairs rather than the internal routing choices.The models have different expected costs.Source: §2 · p. 3
• A client organization acts as Principal and a model provider as Agent; the provider chooses between high- and low-quality routing policies with different costs.The provider's routing decisions are hidden from the client, creating moral hazard when high-effort routing costs more.Source: §2 · p. 3
• The client evaluates each prompt-response pair into a quality signal and pays a nonnegative amount based on the observed signal history when the contract ends.The paper assumes payment at termination for simplicity and notes that other schedules can be implemented with discounting and refunds.Source: §2 · p. 3

• Natural extensions of fixed-duration contracts fail to incentivize πH when clients can terminate based on past performance in iid Bernoulli pass/fail settings.Source: §3 · p. 4
• Under τpass, step-wise contracts favor πL when pcL < qcH, including repeated payments for successful tasks.In HAL, Claude Opus 4.1 versus Claude-3.7 Sonnet has p/q = 0.61/0.5 = 1.22 and cH/cL = 27.03/8.05 ≈3.36; the passage says this condition is often met in current practical settings.Source: §3 · p. 4
• The optimal fixed-duration contract also fails under a simple stopping rule, so its fixed-horizon design does not resolve the problem.Source: §3 · p. 4
• Under τfail, all-success pay favors πL because stopping follows a failure, making payment zero while low-quality routing costs less.Source: §3 · p. 5

4 ANYTIME CONTRACTS

• An anytime contract must make the high-effort policy at least as attractive as low effort for every stopping rule in the prescribed class.The design minimizes the maximum theoretical transfer while satisfying these incentive constraints.Source: §4 · p. 5
• The budget-optimal contract implements the high-effort policy under stopping-time uncertainty, with payment determined by a likelihood-ratio threshold.Its proof avoids linear-program duality and permits generalizations to unbounded integrable stopping and possibly infinite signal spaces.Source: §4 · p. 5
• The minimum-budget characterization also expands the frontier of contract design in non-robust settings.The proof’s direct measure-theoretic approach avoids the linear-program duality used in prior finite-horizon results [23, Thm. 1].Source: §4 · pp. 5–6
• The contract's threshold is also an anytime-valid likelihood-ratio test, and Ville’s inequality bounds an honest provider’s denial-of-payment probability by α uniformly over stopping rules.The budget-optimal contract uses the strictest threshold, α = 1.Source: §4 · p. 6

4.1 Computing Anytime Contracts

• For finite signals and bounded horizons, dynamic programming verifies the worst incentive violation, and binary search finds the minimum feasible budget.The method first checks finiteness of the budget; each verification and finiteness check takes O(n) arithmetic operations and oracle calls.Source: §4.1 · p. 6
• When histories can be merged by signal counts, computation is polynomial in T and takes O(T^2) in the i.i.d. Bernoulli setting.The full history tree can have O(|S|^T) nodes, but equivalent-count histories reduce the computation to O(T|S|).Source: §4.1 · p. 6

• A betting audit uses observed evaluation history to avoid requiring the auditor to know the signal distributions induced by either routing policy.The optimal likelihood-ratio audit requires that distributional knowledge.Source: §5 · p. 6
• For bounded scalar signals and a reference level s0, a predictable betting stake builds an evidence process whose threshold defines the payment audit.The audit can be evaluated sequentially from observed signals alone.Source: §5 · pp. 6–7
• If the provider’s conditional expected quality meets the promised level s0, the audit guarantees payment with probability at least 1 − α uniformly over stopping times.The guarantee follows from the nonnegative-supermartingale property and Ville’s inequality.Source: §5 · p. 7
• When the promised router’s conditional mean equals s0, every admissible stake corresponds to an alternative signal law whose likelihood-ratio audit matches the betting process.The paper’s empirical example also reports that the optimal stake recovers the likelihood-ratio audit.Source: §5 · p. 7

6.1 Qualitative Analysis

• In the synthetic Bernoulli instance, min-pay and min-budget contracts have qualitatively different payment structures under adversarial stopping.Unlike the fixed-duration case, payments under the min-pay optimum are unequal across histories.Source: §6.1 · p. 7
• The synthetic deterrence boundary is non-monotone in alternative success probability, so deterring one policy does not guarantee deterrence of a less accurate, more expensive policy.The paper contrasts this with fixed-duration settings, where the monotone likelihood ratio property yields monotonicity [19, Lem. 3.4.2].Source: §6.1 · p. 7
• The synthetic worst-case exit rule stops when the likelihood ratio is closest to the audit threshold, and can continue when the verdict is already anticipated to drain provider profit.Source: §6.1 · pp. 7–8

6.2 Practical Considerations

• For Claude Opus 4.1 over Claude-3.7 Sonnet, lowering α raises the robustness markup and lowers the worst-case probability of denying an honest provider payment.Longer horizons increase the markup because the supremum covers more possible exit rules.Source: §6.2 · p. 8, Figure 3 · p. 8
• With partial distributional information, the betting audit reaches a global minimum markup of 1 at λ⋆ and remains near-optimal around that stake.The comparison is with the full-information minimum-budget contract for the same model pair.Source: §6.2 · p. 8, Figure 3 · p. 8
• A contract targeting Sonnet 4.5H over Sonnet 3.7H deters every alternative Claude model in the leaderboard, despite a non-monotone, non-convex deterrence set.The contract is designed against one reference model but incentivizes the target over the full listed family.Source: §6.2 · p. 8, Figure 3 · p. 8

7 CONCLUSION & LIMITATIONS

• The framework addresses stopping-time uncertainty and characterizes a budget-optimal contract that remains incentive compatible across admissible stopping rules.The contract is efficiently computable via dynamic programming and supports empirical analysis on synthetic instances and deployed-model data.Source: §7 · p. 8
• The analysis assumes clients have sufficient bargaining power, the interaction is isolated from other market forces, and stopping rules are integrable.It also assumes clients are likely to exercise the most adversarial stopping rule in the prescribed class.Source: §7 · p. 8

AI Use Statement

• Generative AI assisted with proofs, the linear-programming formulation, code, experiment feedback, literature identification, references, and editing.The authors state it was not used to formalize the problem, develop ideas or hypotheses, interpret results, or draft sections.Source: AI Use Statement · p. 9
• The authors checked AI-assisted proofs line by line, reviewed and tested generated code, verified suggested references, and revised AI-edited text.They state that they take responsibility for the final paper and its AI-assisted artifacts.Source: AI Use Statement · p. 9

A.1 Payments depending only on time.

• For time-only payments, the low-quality policy is more beneficial to the provider when the client deterministically stops at T.With payment γ(t), provider utility is γ(T)−cπT, and cH>cL.Source: §A.1 · p. 11

A.2 Step-wise pay-for-performance.

• Step-wise pay-for-performance may fail at τpass whenever p/q<cH/cL, regardless of how large α is.The incentive constraint at τpass is wage-agnostic.Source: §A.2 · p. 11

A.3 Optimal fixed-horizon contracts

• At τfail, if cH > cL and p > q, the utilities always satisfy UπH[w; τfail] < UπL[w; τfail], meaning the H policy has lower utility than the L policy under those conditions.Source: §A.3 · p. 11

A.4 Failure of incentive compatibility in TT

• A minimum-pay-optimal contract can satisfy every deterministic stopping constraint yet fail under an adaptive rule that stops on success and otherwise runs to the bound.The deviation is strictly better for the provider for every cH>0.Source: §A.4 · p. 11

B.1 Linear Programming Formulations

• The min-budget and min-pay formulations are linear programs with one constraint per stopping rule, and are infinite-dimensional when the signal space is infinite or the stopping-rule class is unbounded.In the stated finite case, both programs have |H|+1 variables.Source: §B.1 · p. 12

B.2 Proof of Theorem 1

• The proof derives a lower bound on the budget by taking the supremum of the stopping-rule-specific bounds, then shows the constructed contract attains that budget.The resulting contract is incentive compatible for every stopping rule in the class.Source: §B.2 · p. 14

C.1 Algorithm pseudocode

• The algorithm uses a feasibility verifier with doubling and binary search to return an incentive-compatible contract within ε of B⋆, or report that no finite budget exists.It takes a duration, reachable-history representation, threshold, accuracy, and stopping-reward, likelihood-ratio, and next-signal probability oracles as inputs.Source: §C.1 · p. 14

C.2 Proof of Theorem 2

• Verify(B) finds the largest incentive violation by backward recursion; πH is implemented exactly when VB(∅)≤0, and one pass costs O(n).A maximizing stopping rule stops at the first history where VB equals the stopping reward.Source: §C.2 · p. 15

C.3 Finiteness check

• A finite budget fails exactly when some stopping rule stays below the likelihood-ratio cutoff almost surely under πH yet gives πL higher utility.CheckFiniteness tests this condition with one additional O(n) backward pass.Source: §C.3 · pp. 15–16

C.4 Numerically stable Bernoulli recursion

• Direct likelihood ratios can overflow or underflow; scaling the recursion preserves stopping decisions and the root value while avoiding that numerical problem.The scaled expression uses probabilities bounded by one rather than forming the likelihood ratio itself.Source: §C.4 · p. 16

D.1 Service-level guarantee

• Predictable stakes make E_t a nonnegative supermartingale, so Ville’s inequality controls threshold crossings uniformly over stopping times.The stated conditions include nonnegative betting factors and conditional expected factors at most one.Source: §D.1 · p. 17

D.2 Likelihood-ratio interpretation

• The betting process E_t is exactly the likelihood-ratio process between the promised signal law and the stake-induced alternative; in the Bernoulli case, the matching stake recovers the likelihood ratio exactly.Source: §D.2 · p. 17

D.3 Finding the minimal IC budget for a betting contract

• Feasible betting-contract budgets form a closed interval with a least element Bbet, found by bisection; computing and verifying it requires both policies’ signal laws and costs.Each backward pass takes O(n) operations.Source: §D.3 · p. 18

E.1 Qualitative Analysis

• Figure 2’s reproducibility settings cover minimum-budget versus minimum-pay contracts, the deterred deviation set, and a worst-case stopping rule.The passages specify the Bernoulli parameters and horizons used for each figure panel.Source: §E.1 · p. 18

E.2 Practical Considerations

• The practical analysis uses SWE-bench Verified Mini’s 50-task leaderboard subset, treating reported accuracy as per-step pass probability and total API cost divided by 50 as per-step expected cost.The routers use SWE-Agent entries so that they differ only in the model served.Source: §E.2 · p. 19
• Figure 3’s settings vary α and betting stakes for one model pair, then test a contract against other Claude routers for a second pair.The passage gives the model identities, parameters, horizons, and reference service level for these analyses.Source: §E.2 · p. 19