online service operators

Abstract: Test-time compute (TTC) improves language model responses by spending additional computation at inference time, and the right amount of compute depends on the prompt. Adaptive TTC methods allocate compute based on signals of response quality such as observed rewards, often by stopping once the signal exceeds a fixed threshold, and generally measure cost by the number of generations or tokens. But in online serving, latency is also a cost: it grows with server load, so a method using a fixed threshold spends too little compute when generation is fast and too much when it is slow. For Best-of-$N$ sampling, a widely used TTC method, we propose a two-stage adaptive algorithm that draws an initial batch, then uses the observed rewards and the batch's latency to decide whether to draw a second batch and at what size by comparing expected improvement against predicted cost: it draws one when the first batch's best reward is below a threshold that decreases with the first batch's latency, without explicitly measuring server load. We map each reward to its value under the cumulative distribution function (CDF) of the prompt's reward distribution, so the same tradeoff parameters can be reused across tasks; a regression fitted offline on other prompts predicts a distribution for the CDF value of the first batch's best reward, giving the expected improvement in closed form. We evaluate the method by simulation on a preference-based alignment benchmark, measuring generations-equivalent cost: generations plus latency, converted to generations. The method reaches Best-of-$N$'s reward at lower generations-equivalent cost, and conditioning on the measured first-batch latency saves at least as much of that cost as fixed-threshold (latency-unaware) baselines, and more when latency is highly variable, when it grows with batch size, and when the second batch's latency is highly predictable from the first's.

Abstract: The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair. The natural greedy algorithm connects each terminal pair by a shortest path after making all previously purchased edges free. Awerbuch, Azar, and Bartal (SODA 1996) proved that this algorithm is $O(log^2 k)$-competitive and conjectured an $O(log k)$ bound, where $k$ is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an $O(\log \NumPairs\log\log \NumPairs)$ bound for greedy on a restricted class of inputs, leaving the general case open. In this paper, we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly $Θ(log(k) log log(k))$. Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching $Ω(log(k) log log(k))$ lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $Θ(log log k)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

Abstract: Model providers now face distillation campaigns run through thousands of accounts, each of which looks like an ordinary user. When network and payment metadata cannot link those accounts, the only evidence left is what they ask. We study what a provider can and cannot learn from those queries alone, using one million real chat turns for development and 17 later weeks that no design choice touched for a single frozen evaluation. The answer is set less by anything specific to extraction than by benign coordination: a campaign is visible only if it is more distinctive than the most distinctive group of ordinary users in the same week. We make this precise, show that a small but positive difference between campaign and users buys a detection time rather than detectability, and identify the campaign that is hardest to detect. Empirically, a calibrated monitor catches naive distributed extraction that per-account monitors miss (0.86-1.00 of weeks), and one variant - selecting accounts that move together after discounting how topical each one is - still catches campaigns padded with natural text (0.50-0.96 of weeks) where the other two spectral detectors catch none. Distilling each campaign into a small student shows that, in our testbed, campaigns that evaded every detector kept at most 42% of the capability of a detectable one. The limits are equally concrete: a campaign that ramps up slowly poisons every detector's calibration, benign evaluation pipelines look exactly like distillation, we found no deployable detector at colluder shares of 2.5% or below, and campaigns that relay real users' requests may be invisible to any query-only monitor.