A Two-Layer Framework for Joint Online Configuration Selection and Admission Control
Owen Shen, Haoran Xu, Yinyu Ye, Peter Glynn, Patrick Jaillet
Abstract
We study online configuration selection with admission control problem, which arises in LLM serving, GPU scheduling, and revenue management. In a planning horizon with periods, we consider a two-layer framework for the decisions made within each time period. In the first layer, the decision maker selects one of the configurations (ex. quantization, parallelism, fare class) which induces distribution over the reward-resource pair of the incoming request. In the second layer, the decision maker observes the request and then decides whether to accept it or not. Benchmarking this framework requires care. We introduce a switching-aware fluid oracle that accounts for the value of mixing configurations over time, provably upper-bounding any online policy. We derive a max-min formulation for evaluating the benchmark, and we characterize saddle points of the max-min problem via primal-dual optimality conditions linking equilibrium, feasibility, and complementarity. This guides the design of SP-UCB–OLP algorithm, which solves an optimistic saddle point problem and achieves regret.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning cites Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads
- Efficient Memory Management for Large Language Model Serving with PagedAttention cites Orca: A Distributed Serving System for Transformer-Based Generative Models
Builds on6
- Efficient Memory Management for Large Language Model Serving with PagedAttentionWoosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng et al.SOSP 2023 · 1,016 citations
- Orca: A Distributed Serving System for Transformer-Based Generative ModelsGyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim et al.OSDI 2022 · 690 citations
- Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning WorkloadsDeepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee et al.OSDI 2020 · 286 citations
- Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep LearningAurick Qiao, Sang Keun Choe, Suhas Jayaram Subramanya, Willie Neiswanger et al.OSDI 2021 · 258 citations
- Dual Mirror Descent for Online Allocation ProblemsSantiago R. Balseiro, Haihao Lu, Vahab S. MirrokniICML 2020 · 102 citations
Related papers
- Online Convex Optimization with Continuous Switching ConstraintGuanghui Wang, Yuanyu Wan, Tianbao Yang, Lijun ZhangNeurIPS 2021 · 14 citations
- Online Convex Optimisation: The Optimal Switching Regret for all Segmentations SimultaneouslyStephen Pasteris, Chris Hicks, Vasilios Mavroudis, Mark HerbsterNeurIPS 2024 · 4 citations
- Wait-Less Offline Tuning and Re-solving for Online Decision MakingJingruo Sun, Wenzhi Gao, Ellen Vitercik, Yinyu YeICML 2025
- Smoothed Online Combinatorial Optimization Using Imperfect PredictionsKai Wang, Zhao Song, Georgios Theocharous, Sridhar MahadevanAAAI 2023 · 1 citation
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti et al.NeurIPS 2025 · 7 citations
