Start-time Fair Queueing: Pay-after fair scheduling

This article introduces Start-time Fair Queueing (SFQ)[1], a scheduling algorithm we adopted for a load balancer serving LLM inference.

Each user carries a meter \(S_i\) that records "how much service they have received ahead of others so far." We always dispatch a request from the user with the smallest meter, then immediately add its estimated cost \(c(r)\) to that meter. In other words: "let it through first, then record what it used."

With equal weights, the core is the following single line (see §4.4 for the weighted version).

\[ \boxed{\;i^{*} = \mathop{\mathrm{arg\,min}}_{i \in A}\, S_i,\qquad v \leftarrow S_{i^{*}},\qquad S_{i^{*}} \leftarrow S_{i^{*}} + c(r_{i^{*}})\;} \]

\(A\) is the set of waiting users, and \(v\) is the virtual-time reference point for the competition. On joining or returning, we set \(S_i \leftarrow \max(S_i, v)\), which prevents both banking priority while idle and evading charges by leaving and rejoining (§2.4). Unlike DRR, this scheme has no quantum, so its fairness granularity is automatically one request. The guarantee, however, applies only to the allocation of estimated costs charged by a single scheduler—not to resources such as GPU time consumed after dispatch (§8).

The problem we target

Consider a setting where multiple users (organizations, API keys, and so on) share a fleet of GPU servers. With a single global FIFO, a user who sends a flood of requests fills the queue; with round robin, only request counts are equalized, so a user who sends heavy requests takes a larger share of the processing capacity. What we need is an ordering that, under congestion, splits processing cost — not request counts — roughly equally, and creates no unnecessary waiting when the system is idle.

This is isomorphic to fair queueing in packet scheduling (flow = user, packet = request, packet length = cost), but LLM inference brings the following difficulties.

Indivisible and non-preemptible: once a request is dispatched, it can neither be split nor paused to let others go first.
Large cost variance: costs span several orders of magnitude, from short completions to very long generations, and any formal upper bound shifts with the model and the workload.
Bursty user activity: it is common for a user to send a large burst of requests and then go silent for a long time.

In networks where the maximum packet length is fixed by the MTU, DRR[2], which distributes quanta sized to that maximum, works well. For LLM inference, where the upper bound varies substantially, SFQ's quantum-free pay-after scheme is a better fit. This article addresses the layer that orders dispatch to an existing server fleet, not scheduling inside the inference engine (§6.2).

1. Notation and assumptions

1.1. Users and requests

We place one scheduler in front of each group of servers serving the same model. Each user \(i\) keeps their pending requests in FIFO order, and we call sending the head request to the servers a dispatch. The scheduler decides only one thing: which user with a non-empty waiting queue supplies the next request to dispatch.

1.2. Cost and the sequential model

A request \(r\) carries a cost \(c(r) > 0\) that is fixed at dispatch time. In LLM inference, it is estimated from the input length and the estimated output length, and is never corrected afterward (§5.1, §7.4). The algorithm does not take a maximum value as input, but in the analysis we write \(c_{\max}\) for the largest cost appearing in the interval under consideration.

We use a sequential model that selects one request whenever a dispatch becomes possible. Even if an implementation advances several requests in a batch, the analysis is unchanged as long as it performs a fresh selection for each request (§7.1). Ties are broken by user ID.

1.3. Mapping to packet terminology

The original SFQ paper is written in the language of packet-switched networks. The correspondence with this article's language is as follows, and we substitute terms without further notice.

Original paper's term	This article's term	Concrete entity in LLM serving
Flow	User	Fairness entity: an organization, an API key, etc.
Packet	Request	A single inference call
Packet length \(l\)	Cost \(c(r)\)	Processing work estimated from input length and estimated output length (§7.4)
Weight \(r_f\)	Weight \(w_i\)	Contract or priority (this article's analysis uses equal weights; §4.4)
Transmission on the link	Dispatch to the server fleet	The load balancer sending out a request
Busy period	Period during which waiting requests exist	One contiguous stretch of congestion (§2.5)

2. The algorithm

2.1. The original definition: tags and virtual time

In the original paper, the \(j\)-th packet \(p_i^j\) of flow \(i\) receives the following tags (\(A(p)\) is the arrival time, \(l_i^j\) the length, \(w_i\) the weight).

\[ S(p_i^j) = \max\bigl(v(A(p_i^j)),\ F(p_i^{j-1})\bigr),\qquad F(p_i^j) = S(p_i^j) + \frac{l_i^j}{w_i} \]

The start tag \(S\) is a virtual start time, and the finish tag \(F\) is a virtual finish time. SFQ transmits the packet with the smallest \(S\) and sets the virtual time \(v\) to that \(S\). When a busy period ends, \(v\) advances to the largest \(F\) among transmitted packets. Rather than simulating an idealized model, SFQ derives \(v\) directly from its own operation (§6.1).

2.2. Folding into one variable per user

Within a user, requests are FIFO, so all we need is the start tag of each user's head request. While the queue is non-empty, the next start tag coincides with the previous finish tag, so keeping a single "next start tag" \(S_i\) per user suffices.

Because SFQ dispatches the request with the smallest start tag, the virtual time \(v\) (the start tag of the most recently dispatched request) never exceeds the start tag of any waiting request. When a new request arrives for a user whose queue is non-empty, the previous request's finish tag equals "its start tag + cost"; the start tag is at least \(v\) and the cost is positive, so the finish tag is strictly greater than \(v\). Hence \(\max(v, F_{\text{prev}}) = F_{\text{prev}}\), and \(v\) affects tagging only when a queue changes from empty to non-empty. Section 2.4 gives the rejoining rule for that moment.

In this article, we call \(S_i\) the meter and call advancing it by \(c(r)\) at dispatch charging. Among waiting users, \(S_i\) behaves like cumulative cost aligned with the current baseline \(v\) (§3.1).

2.3. Selection and charging

A single dispatch proceeds as follows (equal weights; see §4.4 for the weighted version).

Select the user with the smallest meter, \(i^{*} = \mathop{\mathrm{arg\,min}}_{i \in A} S_i\) (ties broken by user ID).
Advance the virtual time: \(v \leftarrow S_{i^{*}}\). Since the selected meter is the minimum among waiting users, this corresponds to the original paper's "start tag of the packet in service" (§5.3).
Dispatch the head request \(r\) of \(i^{*}\)'s waiting queue.
Charge: \(S_{i^{*}} \leftarrow S_{i^{*}} + c(r)\). The value after charging is the finish tag of the request just dispatched, i.e. the start tag of the next one.

Immediately before charging we always have \(S_{i^{*}} = v\), and immediately after, \(S_{i^{*}} = v + c(r)\). The meter is charged exactly once, at dispatch, with no corrections and no refunds (§5.1).

2.4. Joining and returning

When a user's waiting queue becomes empty, the user leaves the pool of selection candidates, but the meter retains its value. When a request arrives and the waiting queue changes from empty to non-empty—or when a new user joins—the meter rejoins the competition under the following rule.

\[ S_i \leftarrow \max\bigl(S_i,\ v\bigr) \]

A new user starts at \(S_i = v\). The \(v\) term prevents users from banking priority while idle, while the \(S_i\) term preserves any recent excess service across departures and returns.

The \(S_i\) term in the \(\max\) closes a loophole in the simpler alternative of "always reset \(S_i \leftarrow v\) on return."

Reset-on-return has a loophole. A user who sends one request, waits for it to be dispatched, lets the queue drain, and only then sends the next one returns to the baseline on every rejoin. No matter how much cost the user has accumulated, each request is therefore dispatched at nearly the highest priority. Under congestion, such a sender can build an unbounded lead over users with deep backlogs (§3.3). DRR has no equivalent loophole because a returning flow re-enters at the tail of the circular list.

The meter's residual \(S_i-v\) is at most \(c_{\max}\), and disappears once the baseline catches up (§3.1). What is remembered is at most one recent request's worth.

2.5. Global idle: resetting the competition

When no waiting users remain (the end of the ordering layer's busy period), virtual time advances by the following rule.

\[ v \leftarrow \max\Bigl(v,\ \max_i S_i\Bigr) \]

\(\max_i S_i\) is the largest finish tag assigned so far. This closes the previous competition, and the next period of congestion starts with everyone at the same baseline. The user whose heavy request happened to be dispatched last does not carry a handicap into an unrelated future period of congestion.

At first glance this seems to reintroduce the reset that §2.4 ruled out, but the two have decisively different trigger conditions. Reset-on-return lets one user return to the baseline "while other users are still waiting," whereas the global-idle reset occurs only when no user is waiting—that is, when there is no one left to protect. It cannot occur while congestion continues, so the fairness guarantees are unaffected (§3.4).

2.6. The algorithm as a whole

When a request arrives, append it to the user's FIFO waiting queue. If the queue was empty, first rejoin with \(S_i \leftarrow \max(S_i, v)\) (a new user starts at \(S_i = v\)).
While there is spare processing capacity, repeat the selection, dispatch, and charge of §2.3, one request at a time.
When no waiting user remains, reset the competition with \(v \leftarrow \max(v, \max_i S_i)\) (§2.5).
Completions, failures, and cancellations never modify the meters.

2.7. A small numerical example

Suppose user A's requests all have \(c = 3\), user B's all have \(c = 1\), and both hold sufficient backlogs. The initial state is \(S_A = S_B = v = 0\), with ties broken by user ID (A first). The \(v\) in each row shows the value immediately after step 2 of that dispatch.

Dispatch	\(v\)	Selected	Charge	\(S_A\)	\(S_B\)
Initial	0	—	—	0	0
1	0	A (tie)	+3	3	0
2	0	B	+1	3	1
3	1	B	+1	3	2
4	2	B	+1	3	3
5	3	A (tie)	+3	6	3
6	3	B	+1	6	4
7	4	B	+1	6	5
8	5	B	+1	6	6

A has 2 requests dispatched and B has 6, but both accumulate a total cost of 6. Each meter also stays within the band \([v,v+3]\) at all times, confirming the bound in §3.1.

3. Fairness properties

3.1. The band invariant of the meters

Under the sequential model (§1.2), the following three properties hold at every point in time.

The virtual time \(v\) is monotonically non-decreasing. It never moves backwards.
For every user, \(S_i \le v + c_{\max}\).
For every waiting user, \(S_i \ge v\).

In particular, from 2 and 3, the meters of waiting users always stay within the band \([v,\ v + c_{\max}]\) of width \(c_{\max}\), and no pair of meters differs by more than \(c_{\max}\). The proof is an induction over the state-changing events.

Selection and charge: the new \(v\) is the minimum meter among waiting users, so by property 3 it is at least the old \(v\) (property 1). The selected user's meter immediately after charging is \(v + c(r) \le v + c_{\max}\) (property 2). Every other waiting user's meter is at least the minimum, i.e. at least the new \(v\) (property 3).
Joining and returning: the rejoined meter is \(\max(S_i, v)\); by the induction hypothesis \(S_i \le v + c_{\max}\), so it remains at most \(v + c_{\max}\) after rejoining (property 2), and at least \(v\) (property 3).
Global idle: the new \(v\) is \(\max(v, \max_i S_i)\), which is at least the old \(v\) (property 1), and by property 2 at most the old \(v + c_{\max}\). Since \(v\) only increases, property 2 is preserved, and property 3 holds vacuously because no user is waiting.
Departure: changes nothing.

The initial state with no users satisfies the properties trivially, so the invariant is maintained at all times.

3.2. Cost difference between continuously backlogged users

Let \(W_i\) be the total cost charged during an interval \([t_1,t_2]\). If users \(i,j\) are waiting throughout the interval, neither rejoins during it, so \(W_i=S_i(t_2)-S_i(t_1)\), and the following holds.

\[ W_i - W_j = \bigl(S_i(t_2) - S_j(t_2)\bigr) - \bigl(S_i(t_1) - S_j(t_1)\bigr) \]

Each term on the right has absolute value at most \(c_{\max}\) by the band invariant of §3.1, so we obtain the following.

\[ \boxed{\;\bigl|W_i - W_j\bigr| \;\le\; 2\,c_{\max}\;} \]

Thus, no matter how long the congestion lasts, the cost difference never exceeds two maximum-size requests. This is the equal-weight case of the original paper's fairness theorem.

3.3. No gain from repeatedly leaving and rejoining

For any user \(i\), no matter how many times they leave and rejoin within the interval, the following holds.

\[ W_i \;\le\; v(t_2) - v(t_1) + c_{\max} \]

On the other hand, a user \(j\) who is waiting throughout the interval has the following lower bound.

The former holds as follows. Only two operations change a meter—charging and rejoining—and neither can decrease it, so the cost \(W_i\) charged within the interval cannot exceed the increase in the meter. When the user first becomes a selection candidate in the interval, the meter is at least \(v(t_1)\) (by property 3 if the user is already waiting at the start, or because the rejoining target is \(v \ge v(t_1)\) otherwise). At the end of the interval, the meter is at most \(v(t_2) + c_{\max}\) by property 2. The latter bound follows by subtracting \(S_j(t_1) \le v(t_1) + c_{\max}\) from \(S_j(t_2) \ge v(t_2)\).

\[ W_j \;\ge\; v(t_2) - v(t_1) - c_{\max} \]

Combining the two bounds gives \(W_i-W_j\le 2c_{\max}\). Even by repeatedly leaving and rejoining, a user cannot get more than two requests' worth ahead of a continuously backlogged user. In the other direction, no guarantee applies to capacity that a user never requested.

If we reset \(S_i\leftarrow v\) on every return, this upper bound fails. It is \(\max(S_i,v)\) that preserves the charges across departures and returns.

3.4. Why the global-idle reset is safe

The reset in §2.5 occurs only when no user is waiting. Under the assumptions of §3.2 and §3.3—that some user is waiting throughout the interval—it cannot occur, so the guarantees are unaffected.

Conversely, if every waiting queue has drained, then nobody is competing for capacity at that moment. Carrying service history from one period of congestion into the next would protect no one; it would merely make the user whose heavy request happened to be dispatched last wait at the beginning of an unrelated new period. The original paper closes the competition at each busy period. This can be understood as allowing the pay-after scheme's decaying memory—"remember only the recent excess service" (§2.4)—to expire completely at the boundary between periods of congestion. Moreover, this reset cannot be triggered deliberately: emptying your own queue does not cause it as long as even one other user is still waiting.

3.5. The lower bound on granularity

With indivisible, non-preemptible requests, immediately after dispatching one request of cost \(c_{\max}\), that user is ahead by exactly that amount. The instantaneous skew therefore cannot be brought below \(c_{\max}\), and SFQ's granularity is of the same order as this fundamental lower bound. DRR's granularity additionally includes the quantum \(Q\) (§4.2).

4. Comparison with DRR

4.1. How DRR works and SFQ's pay-after accounting

DRR[2] adds a quantum \(Q_i\) to each flow's deficit counter \(DC_i\) on every visit. While the head packet fits within the balance, it is transmitted and its length deducted; when the queue empties, the counter is reset to 0. If \(Q_i \ge L_{\max}\), at least one packet can be sent per visit, so processing is amortized \(O(1)\).

DRR distributes quanta as credit in advance and dispatches only requests that fit within the balance. SFQ dispatches a request first, charges the full amount to the meter, and then makes the user wait until the others catch up. Large requests never wait for credit to accumulate, and no quantum is needed.

On a single link, letting a heavy job through first directly delays other flows. In LLM serving, by contrast, multiple servers execute in parallel and inflow volume is controlled at a different layer, which makes the pay-after approach easier to adopt (§5.2).

4.2. No quantum parameter

DRR's quantum \(Q\) simultaneously determines the fairness granularity, the computational cost of each round, and the wait after returning from idle. With a fixed MTU, one can set \(Q\) to roughly \(L_{\max}\), but the maximum cost in LLM serving varies with the model and workload. A large \(Q\) makes both granularity and waiting coarse; with a small \(Q\), a heavy request must wait through multiple rounds.

SFQ's granularity is automatically \(c_{\max}\). In exchange, selection requires an \(O(T)\) scan or an \(O(\log T)\) ordered structure. DRR's amortized \(O(1)\) matters in routers handling tens of thousands of flows, but for a load balancer with a few hundred users, SFQ's cost is rarely a concern (§7.1).

4.3. Returning from idle

Neither scheme allows users to bank service credit while idle. DRR resets the counter to 0 when the queue empties, and a returning flow rejoins at the tail of the circular list, where it may wait up to one full round. SFQ rejoins with \(\max(S_i,v)\); if the meter has no residual, the user is eligible for the very next dispatch. Any residual is at most one request's worth and vanishes at global idle (§2.5 and §3.1).

4.4. Weighting

With weights \(w_i\), DRR sets \(Q_i\propto w_i\), and SFQ charges \(c/w_i\). The latter is exactly the definition of §2.1. This article's analysis and examples use equal weights.

4.5. Comparison summary

Aspect	DRR	SFQ
Per-user state	Deficit counter (credit balance)	Meter \(S_i\) (the next request's start tag)
Global state	Current position in the circular list	Virtual time \(v\)
Selection	Traverse the circular list	argmin over waiting users
Cost handling	Distribute quanta in advance, consume on send (pay-before)	Charge at dispatch (pay-after)
Cost information required	Exact cost (packet length in the original paper)	Any value fixed at dispatch (an estimate suffices)
Parameters	Quantum \(Q_i\)	None
Fairness granularity	On the order of \(Q + L_{\max}\)	\(c_{\max}\) (interval cost difference \(\le 2c_{\max}\))
Cost per decision	Amortized \(O(1)\) (when \(Q \ge L_{\max}\))	\(O(T)\) scan (\(O(\log T)\) with an ordered structure)
Intended scale	Thousands to tens of thousands of flows in a router	Tens to hundreds of users per scheduler
Return from idle	Reset counter to 0, rejoin at list tail (worst case one round's wait)	Rejoin with \(\max(S_i, v)\) (immediately a candidate if no residual)
Global idle	No state (each flow already reset on departure)	Advance \(v\) to the maximum finish tag, resetting the competition
Weighting	\(Q_i \propto w_i\)	Charge \(c / w_i\)

5. Design decisions tailored to LLM serving

5.1. Fix the estimated cost and never change it afterward

In packet networks, lengths are known exactly before transmission, but in LLM inference the output length that dominates the processing work remains unknown until completion. Fortunately, SFQ requires only that each cost be a positive value fixed at dispatch time. The properties in §3 continue to hold when that value differs from actual resource use, though the resulting fairness is over the charged values. In the scheme described here, we therefore charge the dispatch-time estimate as is and treat it as final. Correcting the meter later—by applying an additional charge or a refund after the actual output length becomes known—may seem natural, but we do not do so.

Simplicity of the invariant: the one-line rule "a meter is charged exactly once, at dispatch" becomes a collection of state-dependent branches as soon as corrections are allowed: preventing duplicate corrections, handling failures in progress, and so on.
Stability of ordering: output lengths vary widely, and post-hoc corrections would perturb the selection order with noise from past observations. Restricting the quantities used for ordering to values fixed at dispatch makes simulations reproducible and debugging straightforward.
Where calibration belongs: systematic deviations from reality can be absorbed by calibrating the estimation formula against long-run measurements, without settling accounts on individual requests (§7.4). Calibration and the fairness mechanism can evolve independently.

For the same reason, failures and cancellations receive no refunds. If a charged request fails, the user temporarily carries the "unused" amount, but it is at most a few requests' worth and disappears naturally as the baseline advances (§2.4). If requests must be shed under overload, selecting them while they are still waiting and uncharged avoids ever having to cancel and refund an existing charge.

SFQ's use of the start tag also offers a practical advantage when costs are estimates. Selection depends solely on the meter—the accumulation of past charges—so the cost of the request currently under consideration does not affect whether it is selected. That cost matters only when charged, and therefore only for subsequent rankings. An inaccurate estimate does not distort the current decision about which user goes next; it affects only how long that user waits afterward. Finish-tag-based WFQ, by contrast, needs the packet length at selection time and therefore does not provide this separation (§6.1).

5.2. Decide only the order

In the scheme described here, SFQ decides only the order: "whose request advances next." Which server receives it (placement) and whether it is admitted or rejected (admission control) belong to other layers. Whereas the original SFQ divides the bandwidth of one output link, here it allocates positions in the dispatch order to a server fleet; the fairness layer does not see how many servers exist. Keeping fairness, placement, and flow control orthogonal lets each layer be verified independently.

At the ordering layer, this construction is work-conserving. There is no mechanism that holds work back until credit accumulates, so fairness alone never delays a request that can be dispatched. If the selected head request cannot be placed on any server, the interface with the placement layer must decide whether to let a user with a larger meter go first (overtaking) or to stall. Overtaking raises utilization, but the meters alone can no longer explain why that user went first. If explainability of fairness is the priority, stalling is simpler.

5.3. Reinterpreting a single link as a server fleet

The original paper assumes "one link transmitting one packet at a time," and defines virtual time as "the start tag of the packet in service." In a load balancer, dispatch completes instantaneously and dispatched requests execute in parallel on multiple servers, so there is no counterpart to "the one packet in service." Our reinterpretation consists of two changes: \(v\) is "the start tag of the most recently dispatched request" (step 2 of §2.3), and the busy period is "the period during which waiting requests exist" (§2.5). Both are direct reinterpretations of the original definitions over the discrete sequence of dispatch events.

This reinterpretation carries over only fairness of ordering: the §3 properties concerning the allocation of charged cost. The original paper also proves throughput and delay guarantees that assume a link with fixed capacity, as well as robustness of fairness under varying server speeds. Those results depend on a single link and exact packet lengths, so they do not carry over unchanged (§8). For a system in which parallel servers execute dispatched requests and another layer controls the traffic sent to each server (§5.2), however, the ordering layer needs precisely the property that does carry over. Indeed, because this notion of fairness does not depend on processing speed, SFQ can be applied with only a change in interpretation to LLM serving, where execution time varies widely with output length and load.

6. Position among related methods

6.1. The lineage of fair queueing and stride scheduling

The pattern "select the entity with the smallest cumulative amount" recurs throughout the classic fair-queueing literature. The starting point is GPS[4], an idealized fluid model that assumes infinitely divisible work. Among the schemes that approximate GPS with indivisible packets, WFQ[3] simulates GPS to obtain virtual time and selects the packet with the smallest finish tag. SFQ[1] makes two simplifications at once. First, it moves the selection criterion from the finish tag to the start tag, eliminating the need to inspect packet length (cost) during selection (§5.1). Second, instead of simulating GPS, it defines virtual time directly as "the start tag of the packet currently in service," reducing tag computation to a single arithmetic operation. We adopted SFQ for LLM serving precisely because these two simplifications carry over directly.

CPU scheduling uses the same pattern. Stride scheduling[5] selects the client with the smallest pass value and increments that value by a fixed stride inversely proportional to the client's ticket count. SFQ's single variable per user (§2.2) can therefore be viewed as "stride scheduling in which the stride is the cost of each request." In Linux CFS[6], the task with the smallest vruntime—accumulated CPU time normalized by weight—runs next. The min_vruntime value serves as a reference point that prevents newly runnable tasks from receiving excessive retroactive preference, a role similar to that of SFQ's virtual time. Wake-up handling has additional implementation details, so the comparison here is limited to this similarity in roles. In this lineage, DRR is the branch that avoids even tag computation in pursuit of amortized \(O(1)\) operation, while SFQ shows that the simplest tag-based approach suffices at a smaller scale.

6.2. Relation to fairness research in LLM serving

VTC (Virtual Token Counter)[7] is a representative LLM-specific fair scheduler. It is integrated into an inference engine that performs continuous batching. For each client, VTC maintains a weighted cumulative counter of processed input and output tokens, and it prioritizes the backlogged client with the smallest counter. It even raises the counter of a client returning from idle to prevent banking, so VTC and SFQ share the same basic pattern of selecting the smallest cumulative amount.

They differ in where they are inserted and what they are responsible for. VTC replaces the engine's scheduler to make "the volume of tokens actually processed" fair, whereas upstream SFQ sits in front of an unmodified server fleet and makes only "the order in which requests are dispatched" fair. Each server's engine sees only the requests delivered to that server, so a load balancer coordinating the fleet needs a separate layer to make the cross-user dispatch order fair. Conversely, because SFQ's responsibility is limited to dispatch order, it works without engine modifications and does not conflict with placement, admission control, or in-engine scheduling (§5.2). The two methods are complementary rather than competing: they occupy different layers of the system. The limitation that SFQ does not address fairness after dispatch (§8) is the other side of this division of responsibilities.

Research after VTC includes methods that combine token-level fairness with prefix-cache locality[8], as well as methods that jointly address fairness among users and efficiency for the operator[9]. This article is limited to the upstream dispatch-order layer.

6.3. Comparison summary

All methods in this chapter share the pattern of "select the entity with the smallest cumulative amount." Their differences appear along two axes: how they handle a single heavy job and how they handle a return from idle.

SFQ (the method presented in this article)[1]
- Heavy requests: as long as the user's meter is minimal, even a request with cost near \(c_{\max}\) is dispatched immediately, and its full cost is charged exactly once at that moment. The user is then not selected again until the other meters catch up. This is pay-after—"let it through first, then make the user wait"—and over any interval, the cost difference between continuously backlogged users remains at most \(2c_{\max}\) (§3.2).
- On return: under the rejoining rule \(\max(S_i, v)\), users cannot bank priority while idle, and any meter residual above the baseline carries over. A user with no residual immediately joins the group with the smallest meter and becomes eligible for the next dispatch (§2.4). The competition resets only when no waiting users remain (§2.5).
Deficit Round Robin[2]
- Heavy requests: a quantum \(Q_i\) accumulates as credit on each visit, and a heavy request is not transmitted until the balance reaches its length. This is pay-before—"make a large job wait before sending"—and payment is completed by deducting the request's length at send time, with no penalty afterward.
- On return: when the queue empties, the deficit counter is reset to 0, and the flow rejoins at the tail of the circular list. Unused credit is forfeited, and the flow waits up to one full round for its turn.
- Difference from SFQ: the direction of payment is reversed. DRR "saves up and waits before sending"; SFQ "sends first and waits afterward." This distinction determines whether a quantum parameter is needed, whether selection uses amortized \(O(1)\) round-robin traversal or argmin, and whether a heavy request waits before or after dispatch (§4).
GPS[4]
- Heavy requests: GPS is a fluid model that assumes infinitely divisible work. Even a heavy job is processed incrementally and simultaneously with all backlogged flows at weight-proportional rates. There is no notion of an order in which whole jobs are dispatched.
- On return: from the instant of return, the flow receives its weight-proportional share of capacity. Capacity unused while idle is not carried forward, so banking cannot arise in principle.
- Difference from SFQ: the divisibility assumption is the exact opposite of SFQ, which dispatches indivisible, non-preemptible requests whole. GPS is not an implementation target; it functions as the idealized reference that discrete schemes like WFQ and SFQ aim to approximate.
WFQ[3]
- Heavy requests: WFQ dispatches the request with the smallest virtual completion time (finish tag) under GPS. A heavy request has a later finish tag, so it yields to lighter requests before being dispatched whole. Payment is built into the ordering itself: "defer what would finish late."
- On return: an arriving request's tag is computed from the larger of the user's previous finish tag and the current virtual time, so no banking accrues while idle.
- Difference from SFQ: WFQ orders by completion (finish), whereas SFQ orders by start. WFQ needs the request's cost (packet length in the original paper) at selection time and must simulate GPS to obtain virtual time. SFQ needs neither; these two simplifications make it a good fit for LLM serving, where costs are only estimates (§5.1, §6.1).
Stride scheduling[5]
- Heavy requests: stride scheduling selects the client with the smallest pass value, adding on each selection a fixed stride inversely proportional to the client's tickets. Each allocation is a fixed quantum, and "heavy work" is divided into preemptible CPU-time slices, so the accounting never jumps by the cost of one large job.
- On return: a joining or returning client's pass is aligned to the global reference value, preventing banking during dormancy.
- Difference from SFQ: whether the amount added each time is fixed (derived from tickets) or the cost of each job. SFQ's single variable per user can be seen as "stride scheduling whose stride is each request's cost" (§6.1). The difference between divisible CPU time and indivisible requests corresponds exactly to making the stride variable.
Linux CFS[6]
- Heavy requests: CFS runs the task with the smallest vruntime. Execution is preemptible, and the CPU time actually used (normalized by weight) is charged continuously to vruntime—a measurement-based form of pay-after. Heavy work is divided into time slices and interleaved with other tasks, with charges accumulating incrementally.
- On return: using min_vruntime as the reference point, a waking task's vruntime is adjusted so it is not retroactively over-favored (the treatment of sleep wake-ups involves implementation details).
- Difference from SFQ: charging is measured and continuous, whereas this article's SFQ charges the estimated cost in one lump at dispatch and never corrects it (§5.1). The difference between a preemptible CPU and a request that cannot be stopped once dispatched shows up directly in the timing of charging.
VTC (Virtual Token Counter)[7]
- Heavy requests: at each continuous-batching step inside the inference engine, VTC prioritizes the client whose weighted cumulative counter of processed input and output tokens is smallest. A heavy request's counter grows as it is processed, gradually yielding to other clients at token granularity.
- On return: the counter of a client returning from idle is raised to the current level, preventing banking during dormancy. This plays the same role as SFQ's rejoining rule.
- Difference from SFQ: the insertion point and responsibility differ. VTC replaces the engine's scheduler and equalizes "the token volume actually processed," while the upstream SFQ equalizes only "the dispatch order" in front of an unmodified server fleet (§6.2). Charging also differs: incremental addition of measured tokens versus a lump-sum charge of the estimated cost at dispatch.

7. Implementation notes

7.1. Data structures and complexity

Selection consists of finding the smallest meter among waiting users, so an ordered set or priority queue keyed by (meter, user ID) supports each decision in \(O(\log T)\). Each charge or rejoin requires only one removal and one reinsertion, so updates are straightforward. For up to a few hundred users, a simple linear scan on each decision (\(O(T)\)) is fast enough in practice and may be preferable for its simplicity.

The scheduler can be event-driven. On each request arrival or completion, it can run a loop that dispatches one request at a time while placement remains possible. This matches the sequential model in §1.2 exactly. Capping the number of requests handled per event does not change the analysis, provided that selection is repeated for each request.

7.2. Maintaining numerical stability

The meters and virtual time grow monotonically, but only the difference \(S_i - v\) matters to the algorithm. When the values become large, subtracting \(v\) from every meter and resetting \(v = 0\) reduces the range to the width of the band (at most \(c_{\max}\); §3.1) without changing the selection order. This is enough to mitigate floating-point precision loss. After a global-idle reset, the meters of users that have not dispatched for a long time are all at most \(v\) (§2.5), so their state can be discarded without changing behavior.

7.3. Determinism

Breaking meter ties by the lexicographic order of user IDs and avoiding randomness in selection makes the dispatch sequence fully reproducible for a given sequence of events. This determinism is essential when testing the §3 properties through simulation. For floating-point values, a total-order comparison (total_cmp in Rust) is the safe choice.

7.4. Estimating the cost

The cost of an LLM inference is not known at dispatch time because the output length, which dominates the processing work, remains unknown until completion. In practice, a simple formula—a weighted sum of input length and estimated output length—is sufficient. Rather than using the request's output cap (such as max_tokens) directly, one can estimate output length by multiplying that cap by the historical ratio "total actual output length ÷ total output cap." This ratio needs only infrequent updates from long-term aggregates and can be maintained per model or per user.

What matters is that all such calibration happens outside the algorithm. No matter how the estimation formula evolves, the cost of each request is fixed at dispatch time and never changes (§5.1). Because the §3 properties hold for any positive costs, the estimator and the fairness mechanism can be improved independently. This is why the article treats cost as a given value from the outset (§1.2).

7.5. Properties worth testing

The following five properties are useful regression tests. (1) For two users with equal request costs, the difference in dispatched request counts always remains at most 1 (equal sharing). (2) A user whose requests cost 10 times as much receives roughly one tenth as many dispatches (cost fairness). (3) A user returning after a long idle period rejoins at the baseline and gains no priority from the time spent idle (no banking). (4) A user that sends one request at a time and repeatedly drains its queue receives the same share as a continuously backlogged user (no reset abuse). (5) When congestion begins again after all waiting queues have drained, all users start from the same baseline (global-idle reset).

8. Design limitations

Using SFQ in this form entails several trade-offs and limitations.

Fairness applies to charged cost: if a user's actual resource consumption systematically differs from the charged cost, measured fairness is distorted by that discrepancy. The remedy is to calibrate the estimation formula, not to correct individual charges (§5.1, §7.4).
Fairness of ordering, not of execution: only the dispatch order is controlled; post-dispatch GPU time, KV-cache occupancy, and preemption inside the inference engine are not touched.
The original delay and throughput guarantees do not carry over: those guarantees presuppose a single link and exact packet lengths, so our reinterpretation (§5.3) carries only the fairness of cost allocation (§3). No deadlines or maximum waiting times for individual requests are guaranteed.
Within a user, FIFO is fixed: there is no intra-user prioritization or per-request-type control.
A single scheduler is assumed: the meters and virtual time are state held by one process. If the load balancer is replicated, fairness across replicas is outside the scope of this design.
Selection costs \(O(T)\) or \(O(\log T)\): this is unsuitable for processing tens of thousands of flows at line rate, where \(O(1)\) designs in the DRR family are a better fit (§4.2).

9. Summary

There are only three rules: select the user with the smallest meter and charge the cost exactly once at dispatch; rejoin with \(\max(S_i, v)\) when a user joins or returns; and when no waiting users remain, advance virtual time to the maximum finish tag. These are the rules of the original 1996 SFQ, and once a charge is fixed, it is never corrected or refunded.
The guarantee is fairness over the charged estimated cost, limited to the dispatch order at a single scheduler. Over any interval, the cost difference between continuously backlogged users is at most \(2c_{\max}\). Because requests are indivisible, this granularity is of the same order as the fundamental lower bound.
The decisive difference from DRR is pay-after accounting: instead of distributing transmission credit in advance, SFQ dispatches a request first and then records its cost on the meter. This removes the need to tune a quantum, gives single-request granularity, and allows prompt return from idle. The trade-off is \(O(T)\) selection, or \(O(\log T)\) with an ordered structure, which makes the design unsuitable for router-scale flow counts.
Selection depends only on the meters, never on the cost of the request under consideration; virtual time is derived directly from the scheduler's operation; and fairness is defined independently of processing speed. These three properties allow SFQ to be applied with only a change in interpretation to LLM-serving load balancers, where costs are estimates and execution is parallel.

This article is limited to defining the scheme and organizing its theoretical properties. Validation on real traffic, evaluation of cost-estimator calibration, and experiments with weighted operation remain future work.

10. References

The packet-scheduling, CPU-scheduling, and LLM-serving literature discussed or used for comparison in this article is listed below.

[1] Pawan Goyal, Harrick M. Vin, Haichen Cheng, "Start-time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks," SIGCOMM, 157―168, 1996. (Start-time Fair Queueing; the subject of this article)
[2] M. Shreedhar, George Varghese, "Efficient Fair Queuing Using Deficit Round-Robin," IEEE/ACM Transactions on Networking 4(3), 375―385, 1996. (Deficit Round Robin)
[3] Alan Demers, Srinivasan Keshav, Scott Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," SIGCOMM, 1―12, 1989. (Fair Queueing / WFQ)
[4] Abhay K. Parekh, Robert G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," IEEE/ACM Transactions on Networking 1(3), 344―357, 1993. (Generalized Processor Sharing)
[5] Carl A. Waldspurger, William E. Weihl, "Stride Scheduling: Deterministic Proportional-Share Resource Management," Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, 1995. (Stride scheduling)
[6] Ingo Molnar, "CFS Scheduler," The Linux Kernel documentation, 2007. (Linux CFS design document)
[7] Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E. Gonzalez, Ion Stoica, "Fairness in Serving Large Language Models," OSDI, 2024. (VTC: token-level fairness inside the inference engine)
[8] Shiyi Cao, Yichuan Wang, Ziming Mao, Pin-Lun Hsu, Liangsheng Yin, Tian Xia, Dacheng Li, Shu Liu, Yineng Zhang, Yang Zhou, Ying Sheng, Joseph Gonzalez, Ion Stoica, "Locality-aware Fair Scheduling in LLM Serving," arXiv preprint arXiv:2501.14312, 2025. (DLPM: combining prefix locality with fairness)
[9] Zhixiang Wei, James Yen, Jingyi Chen, Ziyang Zhang, Zhibai Huang, Chen Chen, Xingzi Yu, Yicheng Gu, Chenggang Wu, Yun Wang, Mingyuan Xia, Jie Wu, Hao Wang, Zhengwei Qi, "Equinox: Holistic Fair Scheduling in Serving Large Language Models," arXiv preprint arXiv:2508.16646, 2025. (Equinox: integrated treatment of fairness and operational efficiency)

Last Modified: July 12, 2026