Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
Ian D'Ambrosio
Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral rep…
cs.DS2026
Always-Correct Succinct Dynamic Fusion Nodes Are Impossible: A Cell-Probe Lower Bound in the Small-Set, Large-Universe Regime
Ian D'Ambrosio
Kuszmaul, Liang, and Zhou (SODA 2026) ask whether succinct constant-time dynamic fusion nodes exist when the number of stored keys is polylogarithmic in the universe size. We give…
cs.DS2026
A Tight Linear Deterministic Competitive Ratio for Fully Online KV-Cache Scheduling
Ian D'Ambrosio
Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that eve…