Multidimensional Online Resource Allocation for Large Language Model Services under Nonstationary Demand
cs.GT, cs.DS
Submitted: 2023-02-16
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study multidimensional online generalized assignment under nonstationary arrivals, motivated by resource allocation for large language model agent services.
Terminology
Abstract
We study multidimensional online generalized assignment under nonstationary arrivals, motivated by resource allocation for large language model agent services. Providers may commit model and tool allowances to agent tasks upon admission, reserving budgets for their internal execution loops. Each request is rejected or accepted with an irrevocable assignment to one compatible server, earning reward and consuming a vector of its nonreplenishing budgets. Arrivals are independent with known, potentially time-varying type distributions. Scalar reductions can discard feasible combinations of requests with complementary resource requirements. To maximize expected reward, we develop Vector-Aware Best-Fit, which combines linear-programming-guided candidate routing with calibrated acceptance while retaining vector feasibility. Relative to the expected clairvoyant offline optimum, its guarantee improves on scalar reduction in the multidimensional case and has the best possible inverse-dimensional order. With an appropriate acceptance parameter, the proposed policy attains the optimal competitive ratio on all-heavy instances, where every feasible assignment consumes more than half of at least one resource budget. We further develop two heuristics that retain its performance guarantee. Computational results show that the heuristics perform well against benchmarks in most tested settings, especially when capacity is scarce relative to demand.
Sources
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
- Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
- The Power of Multiple Choices in Online Stochastic Matching
- Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack
- Online Weighted Matching with a Sample
- Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments