PaperlayerView exact revision on arXiv

Source-linked AI summary

Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption

Patrick Wong

arXiv:2609.00710v1cs.DScs.LG

TL;DR

LLM platforms must price and admit bundled services when demand and token consumption are uncertain and shared capacities compete. The paper proposes PC-UCB, which clips offline prediction intervals with online confidence intervals, prices resources through shadow costs, and reserves capacity before commitment. It reports robust performance under large prediction error while providing an interpolation regret guarantee and pathwise feasibility, subject to validated prediction radii and other modeling assumptions.

  • Problem

    The paper studies sequential pricing and admission for LLM products when purchase outcomes and stochastic token consumption are uncertain under shared capacity constraints.

  • Method

    PC-UCB intersects validated offline prediction intervals with online confidence intervals, scores products using resource shadow prices, and applies reservation envelopes before commitment.

  • Results

    94.8% of oracle revenue is achieved by PC-UCB in the large-error stress test, versus 90.8% for prediction-only control and 82.5% for online UCB.

  • Takeaways & Limitations

    The framework supports correcting imperfect forecasts rather than either trusting them indefinitely or discarding them, while preserving hard feasibility through reservation checks.

  • Takeaways & Limitations

    The theory assumes a valid prediction error envelope, stationary cell means, bounded resource envelopes, and one-shot arrivals, while the numerical study is synthetic.

Abstract

from arXiv · show

An LLM application often sells or internally allocates several service products: a small or premium model, a short or long token cap, and possibly multiple posted prices. The operational decision is not merely which model answers a prompt. A price changes purchase probability, a token cap changes both user value and the tail of resource consumption, and accepted requests compete for shared compute and premium-model capacity. Demand and output length are initially uncertain, while an offline model may provide useful but imperfect predictions. We formulate sequential pricing and admission with stochastic resource consumption. Each arriving request belongs to an observable segment. The platform chooses a product--price pair or makes no offer; purchase, revenue, and resource use are then random. An offline predictor supplies a uniform, validated error radius for every segment--product cell. We propose Prediction-Clipped UCB (PCUCB), which intersects the offline prediction interval with an online confidence interval, evaluates products using resource shadow prices, and reserves a sample-path envelope before commitment. The prior gives a fast start when accurate, while online learning protects the platform when predictions are coarse. The analysis is modular. On a simultaneous confidence event, regret against a buffered fluid benchmark is bounded by a pacing term plus the cumulative diameter of the intersected intervals. For $J$ segment-product cells and prediction radius $\varepsilon$, this yields \[ \widetilde O\left( \sqrt{T}+(1+\barΛ) \min\{T\varepsilon,\sqrt{JT}\} \right), \] where $\barΛ$ bounds operational shadow prices. Thus the algorithm smoothly interpolates between an almost full-information regime and learning from scratch. Hard feasibility holds on every sample path through reservation envelopes.

1 Introduction

The paper frames LLM service design as sequential pricing and admission under uncertain demand and stochastic token consumption. PC-UCB combines validated offline predictions with online learning, shadow-price resource allocation, and hard reservation safeguards.

  • Motivation: LLM platforms jointly choose model tier, token cap, service attributes, and price, affecting both user value and shared resource load.Premium or longer responses may command higher prices while creating heavier and more variable token workloads.
  • Motivation: Output length and resource use are unknown when offers are made, so expected-consumption planning needs a separate mechanism for sample-path capacity protection.The paper separates economic planning from admission decisions that enforce physical feasibility.
  • Approach: PC-UCB intersects validated offline prediction intervals with online confidence intervals and uses resource shadow prices to score products.A reservation meter then restricts choices using conservative resource estimates.
  • Approach: The framework supports bundled LLM products with stochastic purchase, revenue, and resource outcomes, multiple capacities, and an explicit no-offer action.A reservation envelope prevents an indivisible accepted job from exceeding physical capacity.
  • Contribution: PC-UCB smoothly spans exact-prior shadow-price control and standard online learning when the prior is uninformative.Its interval-diameter analysis quantifies the value of more accurate predictions without requiring a binary choice between using and ignoring the forecast.
  • Evaluation and scope: The study combines synthetic stress testing with a protocol for randomized menus, joint purchase and token-use measurement, and service-quality safeguards.The authors caution that the synthetic study is not evidence about any named provider, population, or market price.

4 Fluid Benchmark and Shadow Prices

The fluid benchmark allocates offering probabilities under aggregate expected-capacity constraints and prices resources through dual variables. A buffer separates the benchmark guarantee from stochastic deviations and final-job feasibility corrections.

  • Deterministic linear relaxation: The fluid relaxation chooses offering probabilities for segment-product pairs subject to expected resource-capacity and per-segment probability constraints.The no-offer action accounts for any remaining probability.
  • Benchmark scope: The benchmark is an upper bound for policies constrained only by aggregate expected capacity, not necessarily the exact offline optimum under indivisible jobs and hard envelopes.The paper therefore compares against a buffered version of the fluid benchmark.
  • Shadow prices: For fixed shadow prices, each segment selects the product with maximum positive Lagrangian score, while resource prices coordinate segment decisions.This converts shared-capacity competition into adjusted product-level choices.
  • Buffered guarantee: A buffer b′ = b−γ1 absorbs stochastic deviations and final-job envelope effects before comparing online revenue with the fluid value.The buffer loss is accounted for separately.
  • Assumption: The analysis assumes bounded optimal dual ℓ1-norms along the segment between buffered and original capacities.This local value-sensitivity condition controls how capacity changes affect fluid value.
  • Degeneracy: Deterministic tie-breaking handles multiple score maximizers without requiring a unique optimal basis or nondegeneracy.The one-step Lagrangian comparison remains valid even when ties change the product mix.

5 Prediction-Clipped UCB

PC-UCB builds confidence-adjusted economic scores from intersected prediction and online intervals, then combines ranking with reservation checks and dual-price updates. Conservative consumption estimates protect capacity while realized use updates scarcity prices.

  • Interval construction: For each segment-product cell, the algorithm intersects online confidence intervals with offline prediction intervals and clips endpoints to [0, 1].The intersection is nonempty on the simultaneous confidence event because both component intervals contain the true mean.
  • Algorithm setup: PC-UCB initializes a buffered capacity, zero cell counts, prediction intervals, reservation envelopes, step size, and bounded shadow prices.Each arriving request is assigned an observable segment before product ranking begins.
  • Admission: The controller ranks products by confidence-adjusted score, appends no offer, and selects the highest positive-score product whose reservation envelope fits remaining capacity.It then posts the price, executes the accepted job, observes revenue and resource use, and updates the selected cell.
  • Interval construction: The effective interval diameter captures the remaining uncertainty after combining the two information sources.The online and prediction endpoints provide optimistic revenue and conservative consumption estimates.
  • Admission: Using an upper consumption endpoint deliberately sacrifices some exploration of uncertain resource-intensive products to avoid treating uncertain token demand as free.This is the safety adjustment that links statistical uncertainty to admission feasibility.
  • Dual update: After realized consumption is observed, projected dual updates raise a resource’s shadow price when usage exceeds its target and lower it when capacity is underused.Because the update uses realized consumption, it reacts to output-length shocks.
  • Implementation: The implementation can use a precomputed menu table, product scans, dominance screening, and a separate premium-model admission layer.Administrative scheduler interventions should be logged as censoring rather than user rejection.

6 Theoretical Analysis

The analysis bounds regret through confidence widths, pacing, buffering, and reservation corrections while preserving hard feasibility. Its interpolation guarantee improves with informative predictions and approaches online cell learning when predictions are uninformative.

  • The theorem decomposes regret into price learning, confidence diameter, buffer loss, and reservation correction.
  • With simultaneous confidence, intersected online and prediction intervals contain the true cell means.The event holds uniformly across cells and times.
  • The cumulative visited-cell width is O(min{Tε, √JT log T}), capturing the transition from prediction-assisted learning to online exploration.The two branches arise by bounding widths by ε or summing inverse-square-root confidence widths across cells.
  • When the prediction is uninformative, regret scales as O((1 + Λ̄)√JT) up to logarithmic and allocation terms.
  • More accurate predictions reduce the statistical term linearly until online sampling becomes more informative than the prior.Further offline improvement can still improve constants and early-horizon behavior.
  • Reservation envelopes preserve hard feasibility on every outcome path, without requiring concentration, a correct forecast, or stationary demand.The reservation meter determines whether a job may physically start, while the learning theorem measures value relative to a fluid benchmark.
  • The guarantee assumes a valid prediction envelope, which can fail after distribution shift and may require enlarging the radius or resetting a product.Empty intersections can otherwise clip away online evidence and create linear regret.

7 Structural Implications for LLM Product Design

The structural analysis treats pricing, model choice, token caps, and resource scarcity jointly through shadow-priced scores and reservation envelopes. It shows why shorter caps and calibrated predictions can retain operational value even when average usage is low.

  • 7.1 The economically relevant quantity is not accuracy per dollar: Shadow-priced scores can prefer a premium model with lower revenue per expected token when its resource mix or segment demand is more favorable.They can also reject an accurate model whose token tail consumes an expensive scarce resource.
  • 7.2 Token caps have option value: A shorter token cap can lower acceptance yet preserve admission when the long-cap product no longer fits remaining capacity.Near exhaustion, the resource envelope rather than the mean determines feasibility.
  • 7.2 Token caps have option value: If a smaller-envelope product has positive adjusted score while an otherwise comparable larger-envelope product is infeasible, the reservation-aware menu weakly dominates the menu containing only the larger product.The larger menu can emulate the smaller one and adds a feasible positive-score alternative.
  • 7.3 When predictions are most valuable: Prediction value rises with short horizons, large segment-product menus, and high shadow-price norms.In constrained premium capacity, token-use calibration may be more valuable than equally sized purchase-probability calibration.
  • 7.3 When predictions are most valuable: Using expected consumption for planning and bounded envelopes for commitment avoids both worst-case underutilization and rare-path capacity violations.

8 Synthetic Experiments

The experiments are organized around four questions, but the supplied passage does not state the questions' content or report experimental outcomes.

  • The numerical study is organized around four experimental questions.

1. Does a correct narrow prediction interval provide a meaningful fast start?

The narrow-error experiment tests whether prediction-assisted control offers an early advantage, while the broader sweep shows when online correction becomes valuable. PC-UCB combines prior information with capacity-aware learning and remains robust as prediction errors grow.

  • Prediction accuracy and fast starts: At ε = 0.18, PC-UCB reaches 94.8% of oracle revenue, versus 90.8% for prediction-only control and 82.5% for online UCB.Online correction recovers approximately four percentage points of oracle revenue over prediction-only control.
  • Capacity-aware control: At ε = 0.18, the myopic controller reaches only 41.2% of oracle revenue and makes no offer on roughly two thirds of arrivals after saturating premium capacity.It leaves much of the general compute capacity unused.
  • Robustness across error regimes: Across the error sweep, prediction-only control is competitive at small errors, while online clipping becomes valuable as the prior becomes coarse.At ε = 0.02, online correction has almost no effect; at ε = 0.18, its value outweighs exploration cost.
  • Capacity-aware control: PC-UCB uses essentially all premium capacity and 99.2% of compute capacity, improving revenue through a different product mix under the same scarce premium resource.The comparison indicates that the gain is not produced simply by refusing more demand.
  • Prediction accuracy and fast starts: At ε = 0.10, prediction-only control reaches 97.3% of oracle revenue versus 96.9% for PC-UCB, showing that exploration is not free.The experiment describes this finite-sample gap as informative rather than evidence against the hybrid policy.
  • Robustness across error regimes: With scarce compute capacity, early exploration can displace later high-value requests, making prediction-assisted policies particularly beneficial.The capacity sweep scales premium capacity proportionally and finds online UCB particularly weak in the scarce regime.

9 Real-Data Evaluation Protocol

The proposed real-data protocol emphasizes randomized identification, explicit measurement of demand and resource use, and validation of prediction intervals. It also treats quality, capacity interference, and interval validity as deployment constraints rather than revenue-only details.

  • Study design: A credible field study should define the analysis unit before collecting outcomes, such as an anonymous request session or organization-day.The product menu should remain small enough to obtain support for every segment–product cell.
  • Study design: The protocol records shown products, prices, exposure, purchase decisions, model and prompt details, generated length, latency, cancellations, refunds, and downgrades.Quality is measured independently through task success, verifier scores, safety checks, or blinded pairwise judgments.
  • Identification: Randomized exploration is needed because historical prices and products reflect latent user value; stratification by segment and time reduces variance.The analysis should report overlap because cells with negligible propensity cannot support reliable counterfactual estimates.
  • Resource measurement: Short token caps censor unconstrained output length, so the observed completion under a short cap cannot be treated as its natural long-cap length.Possible designs include randomized caps, audited shadow generations, or survival models treating cap hits as right censoring.
  • Prediction validation: The offline predictor should be trained on earlier data, calibrated on held-out launch-like traffic, and assigned a radius covering reward and every resource coordinate.Because validity must hold simultaneously across cells, a naive per-cell 95% interval is insufficient.
  • Prediction validation: Prediction intervals must be versioned because model updates, out-of-range price changes, or new traffic sources can invalidate the advertised radius.Empty online–prior intersections are an operational alarm but do not replace prospective validation.
  • Deployment safeguards: Evaluation should report net revenue, coordinate-level capacity utilization, operational overrides, cap hits, no-offer decisions, and discarded resources.Quality and user-protection metrics should be co-primary constraints, including task success, severe-error rate, latency tail, refunds, and service disparity.
  • Deployment safeguards: Capacity-induced interference requires randomized blocks or switchbacks, cluster-robust uncertainty, and always-valid inference or prespecified stopping rules.Organization-day or server-pool-day blocks may be more appropriate than independent-request standard errors.

10 Extensions

The extensions adapt prediction-assisted pricing to continuous prices, drifting demand, repeated users, congestion, and service-level risk. The framework retains shadow-price control and pathwise reservation, but several settings require additional modeling.

  • Continuous pricing: Continuous prices can use fine grids, parametric demand models, or contextual pricing bandits with shadow prices as additive costs.The prediction-assisted interval idea can apply to demand parameters or directly to adjusted revenue.
  • Nonstationarity: Demand drift can be handled with rolling windows or discounting, at the cost of a variation-dependent term.Model releases may require resetting affected cells while retaining information for unchanged prices and segments.
  • User behavior: Repeated users can delay purchases, split tasks across products, or manipulate segment labels, violating the one-shot demand model.Suggested remedies include pricing-schedule commitment, organizational quotas, and incentive-compatible menus; personalized pricing also raises legal and fairness issues.
  • Congestion: Queue-dependent latency couples demand and resource use through congestion, motivating queue-state shadow prices and separate economic and scheduling controllers.Stability then requires queueing analysis in addition to finite-horizon regret.
  • Risk and service levels: Expected resource constraints do not directly control tail latency or emergency-throttling probability.Chance constraints, conditional value at risk, or explicit tail-resource coordinates may be needed beyond per-job reservation envelopes.
  • Scope: The framework combines model tier, token cap, and price decisions with stochastic resource use, shadow prices, and pathwise reservation.Its regret analysis transitions between accurate-prior control and learning from scratch while preserving feasibility regardless of forecast quality.
  • Empirical agenda: The proposed empirical agenda measures purchase and token use jointly, calibrates simultaneous intervals, and evaluates policies at workload level.The synthetic results motivate correcting imperfect predictions rather than either ignoring or fully trusting them.

C Proof of the Confidence-to-Control Theorem

The proof decomposes regret against a buffered fluid benchmark into estimation, pacing, stochastic, override, and buffer terms. Confidence-controlled scores and projected dual updates connect cellwise decisions to the benchmark.

  • Benchmark comparison: The proof compares the policy with true-score maximizers for each segment and includes the no-offer action.A score-comparison lemma relates true and estimated choices before meter overrides are handled.
  • Pacing and dual updates: Projected online gradient descent controls the pacing losses relative to a feasible fluid decision at buffered capacity.The analysis substitutes the dual-update bound into the regret decomposition and adds meter overrides, buffer sensitivity, and confidence-event failure.
  • Stochastic resources: Freedman’s inequality controls stochastic deviations between realized resource use and conditional means.The resulting martingale term is absorbed by the displayed pacing order and the selected buffer.

D Proof of the Width-Sum Lemma

The width-sum proof bounds cumulative uncertainty by taking the better of prediction and sampling rates, while reservation analysis controls indivisible-job overrides. Confidence-endpoint screening safely reduces the menu on the confidence event.

  • Width-sum bound: The prediction branch contributes Tε, while the sampling branch aggregates cell visits with Cauchy–Schwarz.Taking the smaller branch yields the width-sum bound.
  • Reservation overrides: Reservation overrides occur when the next job envelope cannot fit, even if cumulative realized consumption remains below capacity.A sufficient condition reserves room for stochastic deviation, one indivisible job, and dual-tracking error.
  • Buffer choice: The sufficient override condition is not tight, but the reservation meter preserves capacity for any buffer choice.A small buffer may increase late downgrades or no-offer actions without violating capacity.
  • Menu screening: Confidence-endpoint dominance screening can remove products that are weakly dominated for every nonnegative shadow-price vector.The rule is safe on the confidence event and can reduce a large discretized menu.
  • Menu screening: Larger caps and higher prices cannot be ordered by product attributes alone because acceptance and the full resource vector both change.The controller should screen on estimated revenue and all resource coordinates.

G.1 Menu

The synthetic menu varies model tier, token cap, price, segment value, and resource use, with structured prediction stress and deployment checks. The setup is designed to test robustness while emphasizing operational validity and safeguards.

  • Menu: The menu contains small and premium tiers, short and long caps, and four prices per tier.Prices are (0.24, 0.36, 0.48, 0.60) for small and (0.38, 0.54, 0.70, 0.86) for premium products.
  • Demand model: Purchase probability combines segment base value, tier and cap adjustments, and product price through a logistic model.The resulting choices are meaningful but overlapping across segments.
  • Resource model: Conditional expected compute and premium use depend on segment length, cap, and model tier, while realized resources add bounded shocks and are clipped to envelopes.Rejected requests consume zero resources.
  • Prediction stress: The stress direction biases predicted revenue upward and predicted compute and premium use downward while preserving the advertised sup-norm error bound.The perturbation increases with premium tier, long cap, and high price.
  • Experimental controls: The experiment uses common segment sequences and potential outcomes, deterministic tie-breaking, projected prices, and union-bound confidence bonuses.The dual step is 0.045 and prices are projected coordinatewise to [0, 10].
  • Deployment checks: Deployment requires explicit checks for menu validity, exposure logging, enforceable resource envelopes, prediction coverage, counterfactual support, censoring, quality, and fairness.The protocol also asks how to handle persistently disjoint intervals and rollback thresholds.
Loading 2609.00710v1…