CS Paper Radar

Cold-Start Pricing of LLM Services under Two-Sided Learning

Zhicheng Du, Pinyan Lu, Keyu Wang, Zihe Wang, Xiang Yan, Chunxue Yang

cs.GT ·submitted 2026-11-02 14:25 UTC · v1

Abstract

Online large language model (LLM) services face a pricing cold start: providers initially lack the historical data and user information needed for precise pricing, while users' willingness to pay evolves with repeated use. We formulate this challenge as a \emph{two-sided learning} problem between a provider and a user. The user learns from private usage experience, whereas the provider incurs a serving cost and dynamically adapts prices using only purchase decisions to maximize cumulative profit. The provider's central challenge is to learn to price against an evolving willingness to pay without observing the private experiences driving that evolution. We establish matching upper and lower bounds on the minimax regret over horizon $T$, identifying two cost-dependent regimes. When serving costs are sufficiently low, our Calibration-and-Tracking (CAT) algorithm achieves the optimal rate $Θ(T^{1/3})$. In the higher-cost regime, where the provider must learn whether continued service is profitable, Calibration-and-Tracking with Retirement (CAT-R) attains the optimal rate $Θ(\sqrt{T})$. This phase transition shows that serving costs affect not only profit margins but also the fundamental difficulty of learning to price LLM services. Simulations support the predicted regret scaling and show that our algorithms outperform standard online learning baselines in the evaluated settings.

Closest papers

Nearest neighbours by meaning across the whole index.

Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

cs.LG math.OC ·2026-11-04 ·Hanzhang Qin, Sophie H. Yu, Yuewei Zhang, Zhi-Hai Zhang
similarity 0.66
Abstract

Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with $2^K$ intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing $K$ reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.

0.16

How language model agents reshape price competition

cs.GT cs.LGcs.MAecon.GN ·2026-10-15 ·Martin Bichler, Philip Hierhager, Kassian Köck, Fabian Pieroth
benchmark similarity 0.66
Abstract

Repeated Bertrand competition is a stringent benchmark for algorithmic pricing: in homogeneous-goods markets, standard learning procedures typically select the stage-game Nash outcome with prices near marginal cost. We show that LLM pricing agents can escape this benchmark, depending on deployment decisions. LLMs outperform standard online learners through faster adaptation, but this advantage largely disappears against full-information learners. An extracted surrogate algorithm illustrates how LLMs in specific deployments profit from regularly undercutting slower learners. Agents that post one price every period from raw market histories that include rival prices can sustain supracompetitive regimes in self-play. Agents that periodically emit probability distributions from summarized histories of their own profits instead move toward the competitive region in self-play. Markets mixing these interfaces can generate dynamic regimes in which LLMs establish a high-price anchor and regularly undercut it to capture demand. These regimes can keep both competitors' prices above marginal cost. Deployment choices shape these outcomes, shifting the focus from stationary equilibria to dynamic pricing regimes.

0.19

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

cs.DS cs.LG ·2026-09-01 ·Patrick Wong
benchmark similarity 0.64
Abstract

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.

0.18

Optimal Online Learning in Bilateral Trade Through Interest

cs.GT ·2026-11-01 ·Mengfan Ma, Haoyu Song, Yiran Tong
similarity 0.64
Abstract · 52 pages, 5 figures

We consider online learning in bilateral trade on platforms such as Uber, Airbnb, and eBay. In each round, a platform posts a payment to a seller and a price to a buyer, both with private valuations, and observes only whether trade occurs. Its objective is to maximize cumulative gains-from-trade, the sum of the differences between buyers' and sellers' valuations across completed trades. We measure the platform's performance by its regret against the best fixed common price. Financial self-sufficiency motivates global budget balance (Bernasconi et al., 2024), which allows profits from some trades to subsidize others, provided that the final balance is nonnegative. Such financial planning should also account for the time value of money: profits earned earlier can accumulate interest, providing additional funds for future subsidies. Motivated by this observation, we introduce global budget balance with interest, under which a platform starting with no funds can use both trading profits and accrued interest to finance subsidies. For a horizon of $T$ rounds and a fixed exponent $θ\ge0$, we consider the per-round interest rate $r_T = T^{-θ}$. We study two classic valuation models, adversarial and correlated i.i.d., and obtain tight bounds on regret against the best fixed common price in both. As the interest rate grows, optimal regret in each model drops from $\tildeΘ(T^{3/4})$ to $\tildeΘ(T^{5/7})$. The intermediate rates differ: $\tildeΘ(T^{3θ/4})$ for adversarial valuations when $20/21 < θ< 1$, and $\tildeΘ(T^{(2θ+3)/7})$ for correlated i.i.d. valuations when $1 < θ< 9/8$. Finally, as an extension, we study $α$-regret, with approximation factor $α\ge1$, for adversarial valuations against the best feasible distribution over price pairs, and show that the optimal competitive ratio rises from 2 to 3 as interest strengthens.

0.36

Keep, Customize, or Exit: Default Design and Token Pricing in LLM Reasoning Services

cs.GT cs.AIcs.LGeess.SY ·2026-08-13 ·Ahmet Bugra Gundogan, Yigit Turkmen, Melih Bastopcu
similarity 0.63
Abstract

We study a large language model (LLM) service in which a provider chooses a per-token price and a default reasoning-token allocation, while a user may accept the default, customize the allocation, or exit. Larger allocations can improve accuracy but increase token cost and latency. We model this interaction as a Stackelberg game and derive the user's unique optimal customized allocation in closed form. For any price, the acceptable defaults form either an empty set or a compact interval. We characterize the provider's optimal default through a three-regime rule, reduce equilibrium computation to a one-dimensional price optimization, and prove the existence of the equilibrium. We further show that defaults affect the implemented reasoning allocation only when users value the convenience of avoiding customization; otherwise, every service-providing outcome implements the user's optimal customized allocation. Experiments with two compact open-weight reasoning models on five mathematics and science benchmarks support the accuracy-token model and show how model and task characteristics determine equilibrium prices, defaults, and reasoning allocations.

0.04

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

cs.LG ·2026-09-29 ·Wansoo Choi, Seoungbin Bae, Dabeen Lee
similarity 0.63
Abstract

We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a $d$-dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution $\mathcal{D}$, and its departure probability is determined by a logistic model of that context vector with an unknown parameter $θ^*$. The server learns from service outcomes while deciding which waiting job to serve and whether to idle, aiming to minimize queue-length regret, the gap between its expected terminal queue length and the minimum achievable by an admissible policy. Once selected, a job must be served until completion, and we refer to this as the nonpreemptive setting. A central challenge is that, even with full model knowledge, the optimal policy cannot in general be characterized by a simple myopic rule, since the optimal action can change with the remaining horizon at the same queue state. Nevertheless, when the model and horizon are known, the optimal action can be obtained through a finite-horizon Bellman recursion. Motivated by this, we propose Learn--Clear--Plan (LCP), which estimates the system and uses the resulting Bellman recursion to make horizon-dependent decisions. LCP achieves $\widetilde{O}(\sqrt{d/T})$ queue-length regret, while a lower-bound construction gives $Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})$ regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when $T\ge d^2$. When the horizon is unknown, no horizon-independent policy achieves vanishing regret against the finite-horizon optimum. We therefore use SEPT, the policy that serves a waiting job with the highest probability of departure, as a fixed reference, and suggest an estimated-SEPT algorithm that achieves a tracking error of $\widetilde{O}(\sqrt{d/t})$ without knowing the model.

0.18

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

cs.LG ·2026-09-24 ·Naram Mhaisen, George Iosifidis
top venue similarity 0.63
Abstract · To appear in the proceedings of NeurIPS 2026

We study dynamic regret in online convex optimization with an \emph{indicator switching cost}: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, $\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\})$, where $\mathcal{R}^{\mathbf{1}}_T$ is the dynamic regret plus the cumulative indicator switching cost, $S_T$ counts comparator switches, and $P_T$ is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of $S_T$ or $P_T$: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.

0.54

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

cs.LG math.OC ·2026-09-23 ·Jiameng Lyu
theory similarity 0.62
Abstract

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

0.07