{"id":"87891fc0-7081-4173-9f1f-c5960931b26a","arxiv_id":"2501.14312","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A deficit-round-robin scheduler layered on longest-prefix-match batching gives LLM serving both prefix-cache locality and bounded fairness between clients.","lead":"This paper presents DLPM, a scheduler for AI language models that preserves the speed of shared-prefix work while preventing one client from hogging the GPU. It adds fair-sharing counters to a speed-first scheduler, and a distributed version balances fairness, locality, and load across many GPUs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's fairness bound is false: a backlogged client whose request is only in the running batch can miss refills, letting another backlogged client receive unboundedly more service.","rationale":"The reader's weakest assumption was that the fairness proofs require every continuously backlogged client to have a request in the scheduler queue at refill time. My stress-test confirms that this is the load-bearing assumption, but it fails for a more basic reason than the reader stated: it is false even in the synchronous algorithm as written, because a client with a request in the running batch is not in the dispatch Queue and can be skipped by refills. The concrete counterexample shows the Theorem 4.1 bound is not merely unproven; it is incorrect. The paper's central advertised contribution is the fairness guarantee, so this invalidates the main theoretical claim. The empirical results may still be practically useful, but the paper's headline assertion of a rigorous locality-fairness trade-off with a bounded service difference does not hold for the stated algorithm. The verdict should move from CONDITIONAL to REJECT until the proof is corrected or the algorithm is modified to ensure that continuously backlogged clients with running requests are included in the refill trigger. The reader's suspicion about asynchronous implementation is a symptom of the same underlying gap: the algorithm's refill logic does not track backlogged clients uniformly.","tokens_in":22236,"tokens_out":25633,"duration_ms":245529,"concrete_test":"Run a discrete-event simulation of Algorithm 1 exactly as written with two clients: A sends one request with 10 input tokens and 1000 output tokens; B is continuously backlogged with requests of 10 input and 10 output tokens. Set Qu=10000, M=1010, we=1, wq=2, and make A's prefix strictly longer than B's so LPM orders A first. Run for 1000 decode steps and record W_A, W_B, and the refill counts K_A, K_B. If |W_A−W_B| exceeds 2*(U+Qu)=2*(1*10+2*1010+10000)=24060, or if K_A≠K_B during a period when both clients are backlogged, Theorem 4.1 is falsified. Repeat with A's output length 10000; the service gap should grow linearly with output length, confirming the bound is not a constant independent of t2−t1.","verdict_should_be":"REJECT","load_bearing_attack":"The proof of Theorem 4.1 (and the D2LPM theorems that build on it) assumes that two continuously backlogged clients f and g have been replenished the same number k of times (Theorem 4.1 proof, first bullet; Appendix A.1). This equal-k claim is not guaranteed by Algorithm 1. The refill trigger at Lines 4-7 scans only clients with requests in the dispatch Queue; a client whose request is in the running batch B is invisible to the trigger. If that client's deficit qi is positive at a refill event, Line 7 does not replenish it, and its positive qi does not block other clients from being refilled. Thus a continuously backlogged client with a long-running request can receive far less service than another continuously backlogged client whose requests keep the queue nonempty and trigger many refills.\n\nConcrete counterexample within the algorithm as specified: set Qu=10000, M=1010, we=1, wq=2, so U=we*Linput+wq*M=1*10+2*1010=2030 and 2(U+Qu)=24060. Client A sends one request with 10 input and 1000 output tokens (cost 2010). Client B is continuously backlogged with requests of 10 input and 10 output tokens. After the initial simultaneous refill, A's qi stays positive (~7990) while its single request decodes, so A receives no further refills; B's qi repeatedly falls to ≤0, triggering about 15 refills and receiving on the order of 75000 service over 1000 decode steps. At completion W_A≈2010 while W_B≫24060, so |W_A−W_B| exceeds the advertised bound. The root cause is the proof's assumption, not merely implementation asynchrony: even in a fully synchronous execution, a backlogged client with no request in the dispatch Queue is excluded from the refill trigger. The bound in Theorem A.1 may still hold per-client, but the equal-k step, and therefore Theorem 4.1, is invalid.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DLPM, a single-worker LLM serving scheduler that combines Longest Prefix Match (LPM) request ordering with per-client deficit counters, and D2LPM, a distributed extension with per-client-per-worker deficits. The central advertised contribution is a fairness guarantee: for continuously backlogged clients, the difference in weighted service is bounded by 2(U + Qu) in the single-worker case (Theorem 4.1) and by 2|W|(U + Qu) in the distributed case (Theorem 5.1), while preserving high prefix-cache locality. The evaluation on top of SGLang with four workloads reports up to 2.87x higher throughput than VTC and up to 7.18x lower victim-client latency than Preble and RR+LPM.","tokens_in":22634,"tokens_out":16745,"duration_ms":161512,"significance":"If the fairness bounds were valid, the paper would make a useful contribution: adapting the deficit-round-robin mechanism to prefix-locality-aware scheduling is a natural and plausible way to navigate the fairness-locality trade-off, and the empirical results suggest practical benefits over existing schedulers. The theoretical guarantees are, however, the paper's headline claim and appear in the abstract and contributions. The proofs are informal, contain arithmetic errors, and rely on an unstated synchronous-refill assumption; as stated, the single-worker bound is not established and admits a counterexample within Algorithm 1. The paper does not provide an artifact or machine-checked proofs, so the informal proofs are the only evidence for the central guarantee.","major_comments":[{"comment":"The first bullet of the proof of Theorem 4.1 assumes that two continuously backlogged clients f and g 'have been replenished the same k number of times in Line 7 since t1.' Algorithm 1 does not guarantee this. The CHECK_REFILL procedure (Lines 3-8) scans only clients with requests in the dispatch Queue; a client whose request is in the running batch B is invisible to that scan. If such a client has positive qi at a refill event, it is not replenished, and its positive qi does not block other clients from being replenished. With the stress-test parameterization Qu=10000, M=1010, we=1, wq=2, so U=2030, let f have a request with 10 input and 1000 output tokens in B while also having a nonempty dispatch queue (so f is backlogged under Definition 3.1), and let g continuously have small requests in Queue. After the initial refill, f's qi stays near 7990 during its long decode; g's qi repeatedly falls to at most 0 and is replenished roughly every 10000/30 small requests, giving g about 75000 service over 1000 decode steps while f receives about 2010. Then |Wf - Wg| is far larger than 2(U + Qu) = 24060, and the gap grows with the number of refills. The equal-k assumption is load-bearing for Theorems 4.1, 4.2, 5.1, and 5.2; the authors must either prove equal-k under the stated backlog definition or amend Definition 3.1 and Algorithm 1 and re-derive the bounds.","section":"Sec. 4.2, Theorem 4.1; Algorithm 1, Lines 3-8"},{"comment":"The induction proving the invariant qi(t) > -U has a double error in the decode step. First, the statement 'the number of decoded tokens cannot exceed the server's maximum token capacity M, so n * |{r | client(r)=i, r in B}| <= M' is false when n > 1 decode steps occur: a client with k tokens in the batch consumes n*k output tokens over n steps, which can exceed M. Second, from qi(t) > -U one cannot conclude qi(t) - wq*M > -U; the inequality goes in the opposite direction. Because the invariant is not preserved, the bound |Wi(t1,t2) - Ki*Qu| <= max(Qu,U) is unproved, and Theorem 4.1's final inequality, which invokes Theorem A.1, is unsupported.","section":"Appendix A.1, Theorem A.1"},{"comment":"The proof of Theorem 5.1 states that a backlogged client 'will have a request and hence be backlogged in all workers' and that 'requests will be distributed to all workers and credit for each worker is exhausted, before replenishing the credits for all workers.' Nothing in Algorithm 2 ensures this. SELECT_WORKER dispatches each request to a single worker (Lines 13-15), and the per-worker deficit qi,w of a worker that receives no traffic from client i can remain positive while other workers are refilled; there is no mechanism that exhausts every worker's credit for a client before refilling. Thus the |W| factor in the distributed bound is unsupported independently of the single-worker flaw in Theorem 4.1.","section":"Sec. 5.2, Theorem 5.1 and Appendix A.2"}],"minor_comments":[{"comment":"The displayed expansion of Wg - Wf in the proof of Theorem 4.2 is algebraically inconsistent with the definition Wf = qf(t1) + k_f Qu - qf(t2). As printed, the second parenthesized term contains '+ kt1_f Qu' where the preceding minus sign requires '- kt1_f Qu'; the formula therefore does not follow from the definitions.","section":"Sec. 4.2, proof of Theorem 4.2"},{"comment":"The line-number references in the proof are stale: the decode deduction is Algorithm 1 Line 26, not Line 23; the admission deduction is Line 23. This makes the argument harder to audit.","section":"Appendix A.1, Theorem A.1"},{"comment":"Several data points are absent from Fig. 7 without enough explanation: Preble at D=1 is omitted by design, but the S2@Tree-of-Thoughts D=8 point is also missing and the caption's 'takes too long' note does not state whether this is an experimental timeout or a resource limitation.","section":"Sec. 6.2 and Fig. 7"},{"comment":"The abstract's 'up to 7.18x lower latency' claim should name the comparison baseline and workload explicitly; Section 6.2 reports 7.18x versus Preble and 9.55x versus RR+LPM, and the abstract's phrasing is ambiguous.","section":"Abstract and Sec. 6.2"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Theorem 4.1 is not a presentation issue: the equal-refill-count assumption is load-bearing and is contradicted by the algorithm's own refill trigger, and the counterexample is within the manuscript's definitions. The empirical study may still be valuable, but the advertised fairness guarantee must be re-derived under a precise, stated backlog condition or the algorithm must be modified so that the bound actually holds. If the authors cannot repair Theorem 4.1 within a revision, I would not recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's central claim, the fairness bound in Theorem 4.1, is not established. The stress-test note is right. Algorithm 1's refill trigger (Lines 4-7) only scans clients with requests in the dispatch queue. A continuously backlogged client whose only request is in the running batch is invisible to that trigger; its qi can stay positive for a long time while other clients are refilled repeatedly. The proof's first bullet asserts that two backlogged clients have been replenished the same number k of times, but that equal-k step does not follow. The counterexample is concrete and works in a fully synchronous execution. So the advertised 2(U+Qu) bound is not guaranteed.\n\nThat said, the paper has real value. The problem it targets is genuine: VTC ignores prefix locality, LPM ignores fairness. Combining DRR-style deficit counters with LPM ordering is a natural and promising mechanism, and the distributed D2LPM with per-client per-worker deficits is a reasonable extension. The empirical evaluation is broad and shows large improvements over VTC, Preble, and RR+LPM on several workloads. The authors also honestly discuss limitations like prefix sharing across clients and in-program data dependencies.\n\nThe soft spots beyond the proof gap are less serious. The definition of \"backlogged\" in Definition 3.1 is ambiguous; if it means \"has a request in the dispatch queue\", the counterexample does not apply, but then the theorem covers fewer cases than claimed and the proof still does not address running-batch clients. The evaluation lacks error bars, code/data release, and the exact Qu/Qw hyperparameters behind the headline numbers. A prefix-aware VTC baseline would isolate the scheduling contribution from the cost-function change.\n\nWho is this for? Systems researchers working on LLM serving. The empirical story may survive a corrected proof—DLPM likely does improve the locality-fairness tradeoff in practice—but the paper's main theoretical contribution, as written, is unsupported.\n\nI would send this to review. A serious referee should ask the authors to fix the proof or modify the algorithm (e.g., treat clients with running requests as queue-present for the refill check), and to release code and data. If those are fixed, the paper could be solid. As is, I would not cite the fairness bound.","headline":"The DLPM fairness theorem is not proven: the refill trigger ignores clients whose requests are in the running batch, so the equal-refill-count step fails and the advertised bound can be violated even in synchronous execution.","tokens_in":23269,"tokens_out":4887,"would_cite":false,"duration_ms":41499,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DLPM is the first LLM-serving scheduler that keeps prefix-cache locality while proving a constant bound on the service gap between backlogged clients.","keywords":["LLM serving","fair scheduling","prefix caching","deficit round robin","locality-aware scheduling","distributed scheduling"],"falsifier":"Run the DLPM scheduler in the real asynchronous SGLang implementation with a continuously backlogged client whose requests arrive in bursts just after refill checks, and compute the service gap between that client and another continuously backlogged client over a long interval: if the gap exceeds 2(U + Qu) on a single GPU, or 2|W|(U + Qu) with |W| workers, then the theorem's precondition is violated in practice.","tokens_in":1536,"feed_emoji":"⚖️","tokens_out":1790,"duration_ms":40769,"temperature":0.7,"pith_summary":"This paper argues that an LLM inference server can keep the throughput benefits of prefix-cache locality without giving up fairness among clients. It introduces DLPM, a single-GPU scheduler that groups requests by longest matching prefix like locality-aware schedulers do, but inserts deficit counters that force the server to periodically serve less-served clients. The central result is a fairness bound: over any time interval, two continuously backlogged clients receive service that differs by at most a constant, independent of how long the interval runs. The paper extends the same idea to multi-GPU serving with D2LPM, where per-worker deficit counters bound how sticky a client becomes to one GPU. A sympathetic reader would care because it offers a concrete knob for the locality-fairness trade-off that previous fair or locality-aware schedulers handled only one-sidedly.","feed_headline":"Fair LLM scheduling that keeps prefix-cache speed","feed_subtitle":"DLPM bounds each client's service gap at a fixed constant while preserving prefix locality and beating VTC up to 2.87x.","key_machinery":"The load-bearing mechanism is a deficit counter per client, borrowed from deficit round robin, overlaid on LPM's prefix-sorted dispatch order. In DLPM, the scheduler sorts waiting requests by matched prefix length; a request is added to the batch only if its client's deficit counter is positive, and the counter is decremented by the weighted service the request consumes, with all non-positive counters replenished by Qu when no active client can proceed. This preserves the local ordering that LPM exploits for prefix sharing while occasionally interrupting it to serve under-served clients. The distributed D2LPM keeps a second set of deficit counters, one per client per worker, so the global scheduler can decide whether to send a request to the worker with the longest matching prefix or to a less-used worker, balancing locality, load, and fairness.","core_discovery":"The paper claims that combining longest-prefix-match scheduling with a deficit-round-robin quantum mechanism yields both high prefix-cache hit rates and approximate max-min fairness. Formally, for any two clients f and g that are continuously backlogged, the difference in their received service over any interval is |W_f(t1,t2) - W_g(t2,t1)| ≤ 2(U + Qu), where U = we·Linput + wq·M is the maximum service a single request can consume, and Qu is the per-client service quantum. The distributed variant, D2LPM, with |W| workers, bounds the gap between the most- and least-served backlogged clients by 2|W|(U + Qu) (Theorem 5.1). The paper also proves that a backlogged client is not served less than a non-backlogged client by more than the same order of constant, and that both algorithms are work-conserving: no GPU sits idle while requests are queued. On measured workloads, DLPM/D2LPM achieve up to 2.87x higher throughput than VTC and up to 7.18x lower latency for well-behaved clients than Preble and RR+LPM.","pith_inferences":["The same quantum-vs-locality mechanism could apply to other per-client affinities in LLM serving, such as adapter (LoRA) locality or model-replica affinity, wherever a scheduler reorders requests to exploit reuse.","The constant 2(U + Qu) grows with the maximum input length and batch token capacity, so for very long-context workloads the slack in the fairness guarantee widens; the paper's own S2@Long-Context QA result shows locality pressure overtaking fairness in that regime.","The theorems assume synchronised refill of backlogged clients' counters; if the live SGLang implementation refills asynchronously, an adversarial arrival pattern could produce a service gap larger than the stated bound, so a formal analysis of asynchronous refill would be a natural next step.","A direct way to test Theorem 4.1 in practice is to instrument the deployed scheduler to record per-client weighted service at fixed intervals and plot the max-minus-min service over time, checking whether the curve stays under 2(U + Qu)."],"forward_implications":["On a single GPU, a server can keep LPM-like throughput while bounding the service gap between continuously backlogged clients by 2(U + Qu), a value independent of time.","In a distributed deployment, D2LPM gives a global fairness bound that scales linearly with the number of workers, while preserving per-GPU prefix locality and avoiding the synchronization overhead of centralized global scheduling.","Compared with fairness-only VTC, DLPM/D2LPM improve throughput by up to 2.87x across the tested workloads; compared with locality-only Preble and RR+LPM, they reduce well-behaved client latency by up to 7.18x and 9.55x respectively.","The quantum parameters Qu and Qw act as a dial: increasing them improves throughput and locality at the cost of looser fairness, so operators can choose an operating point on a new Pareto frontier.","Both algorithms are work-conserving, meaning the fairness guarantee is enforced by reordering dispatch rather than by idling hardware."],"supporting_citations":[{"why":"Defines the fairness properties, the weighted service cost function, and the VTC baseline that DLPM builds on and compares against.","marker":"[42]"},{"why":"Supplies the Longest Prefix Match scheduling and RadixAttention prefix-cache implementation that DLPM preserves locality from.","marker":"[58]"},{"why":"Provides the deficit round-robin quantum mechanism that DLPM and D2LPM adapt for fair, locality-aware dispatch.","marker":"[43]"},{"why":"Preble is the state-of-the-art distributed locality-aware scheduler used as a baseline for throughput and latency comparisons.","marker":"[45]"}],"fun_headline_variants":["DLPM: fair LLM serving with cache speed","Deficit queues: fairness and cache hits coexist","Locality-aware fairness for LLM serving","Fairness with prefix locality: DLPM","DLPM: constant-gap fairness without losing cache"],"cache_read_input_tokens":25216,"weakest_assumption_plain":"The proof assumes that every continuously backlogged client has a request waiting in the scheduler queue at every deficit-refill moment, so all backlogged clients are replenished in lockstep; if requests arrive asynchronously, a client can miss a refill and the advertised bound is not shown to hold.","fun_headline_variants_meta":{"raw":{"variants":["DLPM: fair LLM serving with cache speed","Deficit queues: fairness and cache hits coexist","Locality-aware fairness for LLM serving","Fairness with prefix locality: DLPM","DLPM: constant-gap fairness without losing cache"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001013,"raw_usage":{"total_tokens":4317,"prompt_tokens":1021,"completion_tokens":3296,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":3225}},"tokens_in":637,"tokens_out":3296,"duration_ms":19015,"temperature":1.0,"reasoning_tokens":3225,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:16:06.375953+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the DLPM scheduler in the real asynchronous SGLang implementation with a continuously backlogged client whose requests arrive in bursts just after refill checks, and compute the service gap between that client and another continuously backlogged client over a long interval: if the gap exceeds 2(U + Qu) on a single GPU, or 2|W|(U + Qu) with |W| workers, then the theorem's precondition is violated in practice.","supporting_citations":[{"cited_title":"Fairness in Serving Large Language Models","cited_arxiv_id":null,"evidence_quote":"Defines the fairness properties, the weighted service cost function, and the VTC baseline that DLPM builds on and compares against."},{"cited_title":"Shreedhar and George Varghese","cited_arxiv_id":null,"evidence_quote":"Provides the deficit round-robin quantum mechanism that DLPM and D2LPM adapt for fair, locality-aware dispatch."},{"cited_title":"Preble: Efficient Distributed Prompt Scheduling for LLM Serving","cited_arxiv_id":null,"evidence_quote":"Preble is the state-of-the-art distributed locality-aware scheduler used as a baseline for throughput and latency comparisons."}],"review_version":1}