Dispatch Control for Priority-Based, Multi-Tenant Workflows under Multi-Resource External Rate Limits

Dispatch Control for Priority-Based, Multi-Tenant Workflows under Multi-Resource External Rate Limits Stanislav Kosorin∗ , Trever Schirmer∗ , Leonard Wossnig† , David Bermbach∗ ∗ Technische Universität Berlin, Scalable Software Systems Research Group

{stk,ts,db}@3s.tu-berlin.de † University College London, Department of Computer Science

arXiv:2611.02926v1 [cs.DC] 2 Nov 2026

leonard.wossnig@forgent.ai

Abstract—Workflow engines orchestrate pipelines of activities, which often call external APIs, on a fixed pool of worker slots, the threads that run them. When an API enforces a hard rate limit shared by all tenants and priorities, a throttled call that retries after a backoff keeps its worker slot and starves other tenants. Large Language Model provider APIs are particularly complex: their per-organization caps are low and bind independently on requests and tokens per minute. The operator can neither reconfigure the cap nor observe saturation before a request fails, so classical fair-queuing assumptions do not hold. We present Backpressure, a worker-side admission gate. It checks each call’s cost atomically against shared admission state and enforces fairness over requests and tokens. A denied call releases its worker slot and waits on a durable timer, so waiting no longer blocks execution capacity. We compare against a naive retry, the AI gateway LiteLLM, and the built-in throttle of the workflow engine Temporal. On a workload with three priority classes, Backpressure raises fairness (Jain’s index over each queue’s fraction of its entitled share) from 0.60 to 0.89, where 1.0 is ideal. It also cuts high-priority tail latency roughly 8 × . When tokens are the binding limit, all request-based baselines serve every priority equally, whereas Backpressure keeps the priority order and reaches a dominant-resource fairness of ∼0.99. Admission costs one round trip to shared state, adds no measurable latency when the cap does not bind, and fails open if shared state is unavailable. Index Terms—admission control, fairness, multi-tenancy, workflow engines, rate limiting, multi-resource fairness, LLMs

I. I NTRODUCTION Workflow engines run production pipelines for many tenants as sequences of steps, called activities. Each running activity occupies one of a fixed number of worker slots, the engine’s scarce resource. Activities routinely call rate-limited external APIs, and many tenants and priority classes share one API ceiling. Noisy neighbors can exhaust it, but the operator does not own it and so cannot enforce fairness directly. Large Language Model (LLM) providers are not the only source of such caps, but they are a particularly hard case. Their perorganization caps on Requests Per Minute (RPM) and Tokens Per Minute (TPM) [1]–[3] are orders of magnitude below This work was conducted in collaboration with Forgent AI GmbH, which provided the use case and production insights. S. Kosorin and L. Wossnig are also affiliated with Forgent AI GmbH.

traditional cloud services. The two also bind independently, so the request mix, not request count alone, decides which one saturates. Yet workflow engines have no mechanism to share such a ceiling among tenants. They dispatch by queue state and worker availability and learn of overload only when an HTTP 429 arrives. This leaves operators three workarounds, none of which decides, before a call is sent, which tenant may use the shared cap. (a) In-process SDK retries couple worker concurrency to provider backoff. (b) Engine-native throttles limit dispatch without observing upstream 429s. (c) HTTP retry gateways absorb retries while holding the caller’s connection open [4]–[7]. In every case, a noisy tenant can starve low-volume tenants. Because rejected calls also count against the external cap, the retries turn into a self-inflicted denial of service. Fair-share scheduling itself is well understood, e.g., Weighted Fair Queuing (WFQ) [8] and Deficit Round Robin (DRR) [9], but these algorithms assume that the operator controls the contended resource. Here the cap belongs to the provider and cannot be reconfigured. We present Backpressure, an admission control approach for workflow engines that acts only on the operator’s own workers. A denied request releases its worker slot and defers on a durable timer, so the wait costs no execution capacity. Our prototype is a plugin for Temporal [10]. Before an activity issues its first HTTP call, the worker checks the call’s cost atomically against shared admission state. That state enforces the global cap, a per-priority split, and a weighted fair share per tenant within a priority. A denial returns a precise retry interval for the workflow’s durable sleep. On a cross-priority workload, Backpressure raises fairness from 0.60 to 0.89 (achievement-Jain [11], 1.0 is an even split). It also cuts high-priority tail latency 8 × and drops the 429 share from 23 % to 4 %, at ∼10 % lower mean throughput. When tokens bind, every request-only baseline flattens priority, while Backpressure keeps the configured ordering at ∼0.99 dominant-resource fairness (DRF). Our main contributions are: •

We formalize fair sharing of hard, externally enforced, multi-resource rate limits in multi-tenant workflow en-

(a) Naive retry, engine throttle, or gateway sleeps through 429 backoff on the slot

Noisy tenant

retry

queued, no slot free

P1

served

P1 waits 8 s

(b) Backpressure waits on durable timer, slot freed

Noisy tenant

retry

P1 served P1 served immediately 0

1

2

3

4

5

6

7

8

9

Time since P1 arrival (s) holds the worker slot

waiting (no slot held)

Fig. 1. One worker slot under overload. A high-priority request (P1) arrives at t=0 as a noisy tenant enters a 7 s retry backoff. In (a), the solid bar holds the slot. In (b), the deny frees the slot at once, indicated by a hatched bar.

gines (Sections II and III). We design Backpressure, a worker-side gate that admits each call against shared request and token buckets with priority and dominant-resource fairness, and turns a denial into a durable timer that frees the worker slot (Sections IV and V). • We release Backpressure as open source and evaluate it against three baselines with a mock rate-limited LLM API (Section VI). •

II. BACKGROUND A workflow engine runs multi-step applications on behalf of many tenants. Each step is an activity, dispatched from a task queue to a pool of workers, and occupies a worker slot while it runs. Engines add durable state, at-least-once execution, and deterministic replay, so application code does not reimplement fault tolerance [10], [12]–[14]. They dispatch by queue depth and availability and expose only static priorities and per-queue rate limits as admission controls. Recent work on engine internals improves durability and throughput but keeps this dispatch model [15]–[17]. Downstream services are assumed elastic, and the worker slot is the only limited resource the engine manages. External rate-limited providers break that assumption. Their per-organization ceilings [1]– [3] are hard limits outside the operator’s control, and many other providers impose similar ones: payment processors cap account transactions per second, and SaaS platforms cap query volume. The engine can neither see these global counters nor reserve capacity against them. Overload therefore surfaces only as HTTP 429 Too Many Requests, often with a Retry-After hint, and only after a slot is committed. A. Three failure modes under contention When the cap binds, the three common responses fail differently but with the same consequence. a) Mode A: Oblivious SDK retries: The simplest approach wraps every external call in the provider SDK’s or the engine’s activity-level retry policy. Both treat 429 as transient,

sleep on the worker thread, and retry in place. The slot stays occupied for the entire backoff, and a single noisy tenant can rapidly deplete the worker slots. b) Mode B: Engine-native throttles: Temporal and AWS Step Functions expose per-queue Requests Per Second (RPS) limits, priority keys, and fairness keys. These throttle how fast the engine dispatches work, not how fast it succeeds upstream. Once the provider cap saturates, every dispatched activity returns 429. Re-enqueuing that work at the same priority amplifies the offered load at the cap, the trigger pattern of metastable failure [18]. The throttle is also request-only, so when TPM binds it never engages and behaves like Mode A. c) Mode C: HTTP retry gateways: Gateways such as LiteLLM, Portkey, Helicone, and Kong AI Gateway [4]–[7] are designed to hide retries from application code. They hold the caller’s TCP connection open for the full Retry-After interval. To the engine, the activity remains in-flight and holds its slot, as in Mode A. Across modes, a tenant that ignores the cap consumes worker concurrency in proportion to its retry budget rather than its admitted throughput (Fig. 1). Lowvolume tenants therefore starve for slots even when their own load alone would never be throttled. III. P ROBLEM F ORMALIZATION These failures lead to four requirements that no existing layer meets together. (a) Global visibility against the externally enforced cap, not per-worker estimates. (b) Metering of requests and tokens that stays fair whichever dimension binds. (c) Fair share across tenants and priorities, not firstcome-first-served dispatch. (d) Slot release on deny before the retry interval elapses, which decouples cluster concurrency from provider backoff. We formalize this cooperative-sharing gap as an admission-control problem over a shared, multiresource external cap. A. Setting Consider a workflow cluster serving tenants T = {t1 , . . . , tN } and priority classes K = {k1 , . . . , kM } with total order k1 ≻ k2 ≻ · · · ≻ kM . All activities share one external target that enforces resource dimensions D, each with a hard ceiling of Cd admissions of resource d per unit time. For an LLM provider, D = {RPM, TPM}. Each candidate activity a carries a cost vector c(a) = (cd (a))d∈D : one request and its (estimated) token count. The operator does not own any Cd and cannot raise it on demand. It observes congestion only through rejected admissions (429s), which do not report which dimension bound. Tenant t has weight wt > 0, priority k weight ωk > 0, and queue (t, k) is entitled in proportion to wt ωk . The engine has S concurrent worker slots. We assume: A1 (Static, known caps). Every Cd is fixed and set in the controller. Bucket and share parameters derive from it, so a cap changing without notice invalidates them. A2 (Sole consumer). The cluster alone uses the cap. Outside traffic skips shared state and silently erodes the cap. A3 (Single cap scope). One ceiling set covers the target. Provider sub-quotas (e.g., per model or deployment) each need a bucket set.

B. Admission decisions and required properties At each dispatch tick, an admission rule makes one of three decisions for every candidate activity a. It may admit a and issue the external call, or defer it for interval ∆a while immediately returning the worker slot. It may fail a on terminal errors only (never as flow control). We require five properties of any satisfactory rule: P1 (Cap P respect). For every dimension d, aggregate admitted cost a cd (a) must not exceed Cd in any time unit of dimension d. P2 (Dominant-resource fair share). Under sustained backlog, each queue (t, k) is equalized on the share of its dominant resource arg maxd cd /Cd , weighted by wt ωk . This is DRF [19] applied to admissions. It reduces to WFQ [8], [9] when one dimension binds for all tenants. P3 (Work conservation). The binding dimension’s cap must not idle while any queue is backlogged (a non-binding dimension necessarily idles once another saturates first). Lowerpriority queues consume an empty high-priority queue’s share. P4 (Estimate reconciliation). A cost known only as an estimate (e.g., tokens before the reply) must later be reconciled with its true value. Otherwise its bucket drifts from Cd . P5 (Slot release on deny). A deferred activity must free its slot before ∆a elapses (requirement (d)). C. Fairness-first scheduling P2 and P3 leave open how priority classes and tenant fairness interact. Strict priority (drain k1 before k2 , then k3 ) is fragile under hard caps. A persistent k1 backlog from one tenant can monopolize the cap and starve every lower class. Yet pure fair share without priority cannot meet tiered latency targets. Backpressure thus adopts a fairness-first policy. The per-priority share (L2, Section IV-B) is work-conserving, so k1 may borrow idle capacity from k2 but not starve it when both are backlogged. Tenants within a class get weighted DRF share (L3). D. Scope We address dispatch control only for deployments that satisfy A1 to A3. Beyond a worker-side wrapper, we change nothing in the engine, activity retry policy, or workflow code. The allocator itself descends from WFQ [8], DRR [9], and DRF [19]. What is new is where admission happens: inside the worker, on atomically updated shared state, with denial turned into a durable-timer deferral. IV. D ESIGN Backpressure implements the admission rule of Section III in the worker, directly before each rate-limited call, and leaves the engine unchanged (Fig. 2). A. Admission at the call site The gate takes the tenant t, the priority k, and the call’s cost vector v = c(a). It returns admit, or defer with interval ∆. On defer it does not wait in place but frees its slot and re-enters after ∆ on a durable timer. The gate thus needs nothing from

Worker workflow activities admission gate

(1) admit (3) release

(2) HTTP call

Shared state

Upstream API

nested token buckets

RPM / TPM cap, HTTP 429

added by Backpressure

unchanged

Fig. 2. Admission path of one worker (all run the same gate against one shared state). (1) One atomic operation on the shared buckets returns admit or defer(∆). (2) Only after a grant does the worker itself call the API, so admission state never sits on the call path. (3) Once the provider reports usage, a signed release reconciles the token estimate. Green: added by Backpressure. Gray: unchanged (engine, workers, provider traffic).

the provider, only a durable engine sleep, which most engines offer [10], [12], [13]. B. Nested token buckets Each admission consults three nested layers that jointly enforce cap respect, work-conserving priority, and dominantresource tenant fairness in one decision. L1 (Global cap). One bucket per dimension d, refilled at rate Cd . Admitting a consumes cd (a) from each, a hard ceiling every tenant and priority must clear. L2 (Per-priority share). One bucket P per class k and dimension d, nominally limited to ωk Cd / ω. Work-conserving borrowing passes idle high-priority capacity to the next class in the same tick. L2 is thus a soft yield, not a strict filter. L3 (Dominant-resource fair share). A single share bucket per active (t, k) pair, measured in normalized dominant-resource wt units σ(a) = maxd cd (a)/Cd . It refills at W X ⋆ share units k per second. Here Wk is the live weight sum at priority k, and X ⋆ is the DRF equalization rate [19] X Cd W k cd (t) X ⋆ = min , Dk,d = wt , (1) d Dk,d σ(t) (t,k) active

with cd (t) tenant t’s current per-request cost and σ(t) its dominant share. Dk,d is demand per unit of dominant share, so this refill drives the binding dimension (the arg min) to its cap while keeping weighted dominant shares equal. The weight ωk enters through the L2 shares rather than the L3 rate, so P2 holds within each class. The nested refill is a fluid approximation of DRF, validated empirically (Section VI-C). An admission for (t, k) succeeds only when every L1 and L2 dimension and the L3 share bucket hold enough tokens. All are then debited atomically. Otherwise, the rule returns ∆, the earliest refill time among the depleted buckets. ∆ carries no jitter: synchronized wake-ups are harmless because admission calls are serialized and take milliseconds (Section VI-E), so the

Algorithm 1 Atomic multi-resource admission. Require: tenant t, priority k, cost c, now τ Ensure: ADMIT or DEFER(∆) 1: refill L1d , L2k,d for all d, and L3t,k by elapsed time 2: evict idle (·, k) entries, then scan peers for Wk and X ⋆ 3: σ ← maxd cd /Cd , update L3t,k rate ← (wt /Wk ) X ⋆ 4: if ∀d : L1d ≥ cd ∧ L2k,d ok and L3t,k ≥ σ then 5: debit all buckets by c (L3 by σ) 6: return ADMIT 7: else 8: ∆ ← earliest refill over the depleted buckets 9: return DEFER(∆) 10: end if

first grant debits the bucket and the others are deferred again. Reducing L3 to one shared dominant-share bucket (rather than one weighted bucket per dimension) equalizes dominant share instead of per-resource share. A token-heavy and a requestheavy tenant thus receive their fair split even though they stress different limits. C. Estimate reconciliation and reservation Before the reply, the token component of c(a) is only an input-based estimate. Backpressure debits it at admission and, once the provider reports usage, issues a signed release that debits or refunds the difference (P4). This keeps the TPM bucket aligned with true consumption. A gate that debited only the estimate would over-admit whenever completions run long. Requests above the cap are rejected with 429, and on major providers these failed requests still count against the per-minute limit [1]. A transient burst above the cap therefore wastes rate budget rather than being free. For such workloads, an optional reservation mode debits the completion upper bound (input + max_tokens) up front and refunds the unused share after the call. This trades a little steady-state throughput for much less overshoot. D. Atomic admission on shared state All buckets live in state shared by the worker pool, and one admission is one operation on it (Algorithm 1). The approach asks only that the store serialize this read-modify-write across workers. It needs no lock or consensus round and costs one round trip of O(|Tk |) work. This is the only mutable state Backpressure adds, and the reconciling release is a second, smaller operation of the same kind. Releases are awaited but best-effort. If a worker dies before its release lands, the gate errs conservatively with over-debited buckets and never overadmits (invariant I1 below). Refill erases the residue within a burst window. E. Invariants Admission must be linearizable, which confines shared state to one authoritative copy. The approach does not replicate this copy; if it is lost, the gate fails open (I3) instead of hiding the failure. Three operational invariants follow. I1 (No double counting). Admission atomically checks and debits all dimensions, so concurrent workers cannot overcommit any cap. I2 (No worker-local state). Workers hold

TABLE I W ORKER - SLOT BEHAVIOR DURING THE WAIT. Strategy Naive SDK retry (Mode A) Engine throttle (Mode B) HTTP retry gateway (Mode C) LiteLLM proxy (client-side) Backpressure (ours)

Slot freed

Cap-aware

× × × × ✓

× requests only partial partial both resources

no bucket state. Weights and caps are read from shared state at decision time and may be hot-updated. I3 (Degraded open). The gate fails open (Section V), which preserves availability at the cost of temporary fairness loss. F. Prototype The evaluated prototype is a Python package for Temporal workers, which we publish as open source software1 . Developers wrap external calls in a context manager: async with bp.admit(tenant=t, priority=k, cost=v): response = await provider.call(...)

The shared state is one Valkey primary [20]. On defer the wrapper raises BackpressureRetry carrying ∆, which the workflow turns into workflow.sleep(∆). A deployment adds a thin client to each worker pod and one Valkey node. V. T IMER -BASED D EFERRAL The admission buckets decide when to admit work. Timerbased deferral decides where the wait happens, and that choice separates Backpressure from the alternatives. A. Slot behavior during the wait As Table I shows, all three modes of Section II hold the slot during a denial. Backpressure releases it, as the wait is managed by the workflow runtime, not the worker thread. HTTP gateways cannot release slots because they sit on the call path after the workflow has committed a slot. Even the LiteLLM proxy’s client-side limiter, which pre-empts some overshoot, leaves the activity in-flight and its slot held. Backpressure operates one layer earlier and translates a denial into a durable timer before any HTTP traffic is sent. B. Deferral as a durable timer On defer, the gate hands the wait to the engine: the workflow records the wake time in durable history and sleeps for ∆. Unlike a worker-side sleep, this frees the slot in the same dispatch tick. When the timer fires, the engine re-schedules the activity, possibly on another worker, which runs admission again. High-priority work thus flows through a fleet whose concurrency S is no longer pinned by low-priority backoff. The L3 bucket is shared state keyed by (t, k), so a retry after deferral meets the same depleted bucket. This preserves fairness across activity and worker boundaries. On a cold start, a bucket without stored state is created at full capacity inside the atomic admission call. Concurrent first calls therefore cannot over-admit. 1 https://github.com/3s-rg/backpressure

C. Degraded-open fallback If the admission operation times out or the shared state is unreachable, the gate logs a warning and calls the provider unchanged. During an outage, the system behaves exactly as before Backpressure was installed. I3 thus degrades a failure to the naive baseline instead of losing work. Unit tests and a local fault-injection smoke test verify this path locally: with the shared state stopped mid-run, calls proceed ungated and admission resumes on restore. VI. E VALUATION We run five experiments. E1 (Retry waste). We measure how much upstream retry waste worker-side admission removes under saturation. E2 (Slot occupancy). We test whether timer-based deferral decouples slot occupancy from provider backoff. E3 (Priority order). We test whether the gate preserves the configured priority order under contention. E4 (Fair share). We test whether per-tenant service tracks the configured weighted fair share. E5 (Token binding). We test whether these properties persist when tokens, not requests, bind. A. Testbed and configurations All experiments run on a fixed Google Cloud topology in one zone (europe-west4-a). An e2-standard-4 node runs the worker, and two e2-medium nodes run the mock upstream and Valkey. Temporal uses an e2-standard-2 PostgreSQL host and three control VMs (frontend, history, two matching shards). Valkey is deployed for every run so that all configurations see identical infrastructure. The mock upstream enforces a fixed-window cap of 60 req s−1 , plus 12 000 tok s−1 on the multi-resource ladder. It returns HTTP 429 above either bucket and simulates 50 ms to 150 ms of service latency. These per-second windows compress the providers’ per-minute caps and preserve the request-to-token ratio. Fidelity of the mock upstream. The mock serves an OpenAIshaped endpoint and reproduces the denial signal (rate-limit headers, a provider-shaped error body, Retry-After in milliseconds). A call passes only if both the request and token limiters admit it, so either dimension can bind. A live endpoint differs in three ways. Token cost is estimated from request size rather than a tokenizer, and there are no permodel sub-quotas. Rejected requests do not count against the window, so measured baseline retry waste is a lower bound. We run a fixed window (the limiter also supports sliding windows and continuously refilling buckets) because it is the harder case. Provider capacity arrives in steps while the gate spends it smoothly. The window model never enters the gate’s parameters, which derive from the rate Cd alone (A1), and all configurations meet the same upstream. We compare four configurations. naive uses SDK retry with exponential backoff on 429 (industry baseline). tn (temporal-native) sets Temporal’s matching-service queue-rps-limit=60 plus per-workflow Priority and fairness_key (strongest stock baseline). litellm is the open-source LiteLLM proxy in front of the same upstream,

TABLE II E VALUATION WORKLOADS . Workload

Description

Single resource (60 req s−1 cap, 5 repeats) uncongested one tenant at 25 % of the cap, no contention overload one tenant saturating the cap, isolates retry waste cross-priority six tenants, three classes, concurrency 4/8/16 for P1/P2/P3 Multi resource (adds 12 000 tok s−1 , 5 repeats) request-bound 100-token prompts, the RPM ceiling binds token-bound 400-token prompts, the TPM ceiling binds mixed-dominant 1×800- and 2×80-token tenants, dominant resources differ noisy-estimates random output length, estimates diverge from reported usage reservation noisy-estimates with worst-case reservation (Section IV-C) reservation-capped reservation, completions clamped to max_tokens=200

with client-side limiting. Each tenant’s virtual key gets a static weight-proportional cap slice per 60 s window. The slices total 3600 RPM and 720 000 TPM and sum to the cap without oversubscription. bp is our gate with priority weights ω = (0.5, 0.3, 0.2). We run each (workload, configuration) pair five times. We report means, and figures add 95 % Student-t confidence intervals. The fairnessPmetric is achievement-Jain P over the active queues Q: J = ( q rq )2 /(|Q| q rq2 ). Jain’s index measures how evenly values are distributed. It is 1 when all queues attain the same value and minimal (1/|Q|) when one queue captures everything [11]. A queue’s achievement ratio rq = observedq /idealq is observed service over its WFQ (one dimension) or DRF (several) entitlement. Thus J = 1 means every queue attains the same fraction of its entitled share, not equal raw throughput. B. Single-resource workloads The single-resource workloads (Table II) isolate one effect each. We report cross-priority in full because it maximizes the fairness gap. Its two tenants per class run 4/8/16 workflows for P1/P2/P3. Any slot-proportional dispatch (naive, tn) thus splits the cap 4 : 8 : 16 and inverts priority, with P3 served at ≈ 4× P1’s rate. Backpressure restores the configured staircase in successful RPS (Fig. 3: P1 = 21.3, P2 = 18.5, P3 = 11.8). It lifts achievement-Jain from 0.60 to 0.89 and reduces P1 HTTP p95 about ∼8 × (3506 ms → 415 ms). Mean worker-slot occupancy per call drops 63 % (709 ms → 259 ms). Deferral returns the slot during the wait instead of holding it through a retry chain. Mean OK RPS is ∼10 % lower (55.5 vs 49.6), as the same work spreads over a longer schedule. This answers E1, as the 429 share falls ∼6 × versus naive (23.2 % → 4.1 %), and E2, as slot occupancy decouples from provider backoff. Figure 3 shows bp serving P1 > P2 > P3, while the baselines invert the order toward the cap-blind 1/|T | allocation. This answers E3 (the configured ordering holds) and E4 (per-tenant service tracks the WFQ ideal). litellm holds the lowest 429 share (1.2 %) through client-side limiting but stays priorityblind. P1 receives 7.9 OK RPS, the same as naive, mean throughput falls to 35.4 RPS, and achievement-Jain (0.67) sits far below bp. tn reaches 3.1 % 429s by pinning dispatch, which leaves no backlog to reorder, so its P1 tail is the worst (3692 ms). Overload and uncongested runs corroborate this. On overload (single tenant, no fairness confound), bp cuts

P1

40

34.8

P2

P3

priority inverted 32.0

31.4

priority respected

OK req/s

30 20

17.4

16.1

15.9

21.3 18.5 11.8

10 0

8.4

naive

8.1

7.9

tn

litellm

cap, against 74 % without the refund. Clamping completions to max_tokens reaches 96 % of cap at 3.6 % 429 share, but changes the offered work (not comparable). This answers E5: priority ordering and DRF persist whichever dimension binds.

bp

Fig. 3. Cross-priority OK throughput per class (contention window, 95 % CIs, 5 repeats).

the 429 share from 14.2 to 6.0 %. It also cuts slot occupancy from 412 to 224 ms at the highest throughput of all. In the uncongested run, all four configurations tie within noise on latency and throughput at zero 429s. C. Multi-resource workloads The single-resource results show that the gate works when requests bind. The multi-resource workloads add a 12 000 tok s−1 cap and test whether this still holds when tokens bind (Table III). a) Token-bound workload: When 400-token prompts make TPM bind at ≈30 req s−1 , tn’s queue-rps-limit=60 never engages. tn thus floods the upstream exactly like naive (41.1 % vs 41.3 % 429s). Retuning it to the token-implied rate (≈ 30) would hold only for this prompt size, and no static request ceiling suffices (mixed-dominant). litellm’s client-side limiter roughly halves the waste (17.2 %). bp instead measures tokens directly and cuts it to 6.1 %. Only bp produces a priority staircase under token binding. Its OK RPS is 14.3/8.8/5.9 (P1/P2/P3) versus a flat ≈ 10 for all baselines. Its mean workflow completion is 57.0 s for P1 against 104.7 s for P3, while the baselines stay flat (Fig. 4). DRF Jain is ≈ 0.89 for all baselines (within noise), 0.995 for bp. Worker in-activity stall (act_succeed mean) is ≈ 8× lower under bp (211 ms) than under naive/tn (1634/1677 ms), with litellm at 1452 ms. b) Mixed-dominant workload: Of three equal-weight P1 tenants, one is token-heavy (TPM-dominant) and two are token-light (RPM-dominant). Both caps bind: under bp, 46 % of the 429s hit the request cap and 54 % the token cap. naive and tn let the heavy take 1.76× its fair share while the light tenants get about half of theirs (≈ 0.52/0.55), because equal request counts do not mean equal dominant shares. litellm’s static ceilings do not help (heavy 1.73×, light 0.47), and its DRF Jain (0.69) is the worst. bp limits the heavy tenant to 0.99 and lifts the light ones to ≈ 0.80. DRF Jain rises from 0.72/0.75 to 0.996, which none of the baselines achieve. c) Noisy estimates and reservation: With random completion lengths, admission on input-based estimates alone yields 39.0 % 429s. Reconciliation (Section IV-C) cuts this to 6.0 % at ≈17 req s−1 OK throughput and 95 % of the token cap. P1 HTTP p95 falls to 7.7 s, against 14.5 s under naive. Worst-case reservation holds 3.6 % 429s at 94 % of

D. Ablation: attributing the gains We disable Backpressure’s mechanisms one at a time (Table IV). Gating itself (Section V) removes most of the retry waste. On token-bound, every gated arm cuts naive’s 41.6 % 429 share to single digits, except bp without DRF, which cannot see tokens. DRF has the largest effect on waste when tokens bind. Without it the share jumps back to 38.4 %, close to naive, against 5.8 % with it. Its effect on DRF Jain is smaller (0.959 to 0.997) because all tenants here send the same 400-token prompt. Equal requests then already approximate equal dominant share, so a token-blind gate still allocates fairly and merely wastes the cap. The fairness effect appears once dominant resources differ (mixed-dominant). Priority shaping supplies the ordering. On cross-priority, bp without priority still reaches achievement-Jain 0.839 (full: 0.889), since tenantlevel fair share equalizes the six queues. The index, however, ignores ordering, and only the full gate yields P1>P2>P3. Both layers are needed: DRF handles the binding dimension, and priority shaping handles the class order. E. Gate overhead The gate adds one Valkey round trip per call. In the uncongested run, the cap never binds, so the gate never defers and its overhead is within noise. Worker in-activity time (166 ms) matches naive’s (172 ms), and median HTTP latency is no worse (184 vs 201 ms). litellm’s client-side limiter instead adds ≈50 % in-activity stall on every call (252 ms). Under contention, the gate imposes a wait, but as a durable timer with the slot released, not as held slot time. This deferral (p95 1.9 s on cross-priority) drives the 63 % slot-occupancy reduction. Across 88 000 evaluations the Lua step takes 1.5/4.9/9.0 ms at the median/p95 /p99 . At these rates, the primary stays far below its throughput ceiling (measuring it is future work). F. Trade-offs Priority shaping raises the median of deprioritized classes under contention (P3 on cross-priority). Under mild load, bp’s median matches naive’s. Shaping also lengthens the drain span by up to ≈ 12 %, the same trade an operator opts into by defining priority classes. The work-conserving L2 leaks ≈ 10 % to 15 % across priorities under joint saturation, so strictpriority installations would need a hard filter. Backpressure redistributes the cap rather than raising throughput, and its one Valkey primary serializes every admission, so scaling past it needs sharding by target. VII. R ELATED W ORK We group related work by who owns the bottleneck.

TABLE III M ULTI - RESOURCE RESULTS OVERVIEW ( MEAN OF 5 REPEATS , BEST IN BOLD ). 429 SHARES CARRY 95 % CI S OF AT MOST 1.9 PP. DRF JAIN USES THE POOLED CONTENTION WINDOW. HTTP 429 share (%) ↓

DRF Jain (observed/ideal) ↑

Workload

Binds

naive

tn

litellm

bp

naive

tn

litellm

bp

request-bound token-bound mixed-dominant noisy-estimates reservation reservation-capped

RPM TPM mixed TPM TPM TPM

22.6 41.3 32.8 52.6 52.4 52.9

2.9 41.1 24.2 52.5 52.0 52.1

0.0 17.2 9.5 34.7 34.6 29.2

3.1 6.1 6.7 6.0 3.6 3.6

0.888 0.889 0.722 0.890 0.886 0.881

0.883 0.888 0.753 0.885 0.883 0.893

0.887 0.888 0.694 0.889 0.892 0.885

0.990 0.995 0.996 0.986 0.996 0.998

naive: service heatmap

backpressure: service heatmap

6

t_p2_a P2 t_p2_b P2

4

t_p3_a P3

2

t_p3_b P3

0 0

20

40

60

80

100

time (s)

tenant, priority

t_p1_a P1 8

t_p1_b P1

starved (demand > 0, ok = 0)

t_p1_b P1

10

t_p2_a P2 t_p2_b P2

5

t_p3_a P3

OK requests / s

starved (demand > 0, ok = 0)

OK requests / s

tenant, priority

t_p1_a P1

0

t_p3_b P3 0

20

40

60

80

100

time (s)

Fig. 4. Token-bound service heatmaps. Rows are tenants with P1 on top, blue is served OK req/s, and hatched red marks starvation. Left: naive serves every priority uniformly. Right: Backpressure drains P1 first and P3 last, a priority staircase although tokens, not requests, bind. TABLE IV T OKEN - BOUND ABLATION (5 REPEATS ). Configuration naive (no gate) bp without DRF bp without priority bp (full)

429 share (%)

DRF Jain

41.6 38.4 3.2 5.8

0.878 0.959 0.886 0.997

a) Admission control and overload management: The Staged Event-Driven Architecture [21] and Breakwater [22] decompose services into stages with per-stage admission and closed-loop feedback on locally observed queuing delay. Both assume the controller owns the protected resource. Backpressure extends this line to a worker-side gate before a third-party endpoint whose only congestion signal is a post-hoc 429. b) Fair queuing and distributed rate limiting: Our L3 allocator builds on fair queuing. WFQ [8] and DRR [9] approximate Generalized Processor Sharing [23], an idealized fluid server, at low cost. DRF [19] extends the single-resource objective to multiple resources, for a datacenter scheduler that owns and observes them all. Distributed rate limiters (Raghavan et al. [24], Seawall [25]) likewise assume the enforcing system controls the limited resource and observes queue depths. Industry global rate limiters (Google’s Doorman [26], Salesforce’s coordinated limiting [27]) coordinate clients against a limit the enforcing system owns. Backpressure’s shared admission state instead enforces an externally owned cap that it cannot observe, using configured limits. c) Backpressure in dataflow systems: The term backpressure originates in streaming dataflow, where a slow consumer signals the producer to slow down. Reactive Streams [28] and Flink’s credit-based flow control [29] implement it end

to end. The producer can be slowed because it sits inside the same system. Our setting inverts that assumption, as the bottleneck is a third-party API the operator cannot push back on. Backpressure therefore applies the pressure inward, onto the worker, rather than blocking the source. Serverless dataflow runtimes such as Cloudburst [30] and Kappa [31] cannot push back on external calls either, and neither addresses fair admission against a shared cap. d) Multi-tenant fairness in LLM serving: A large body of work optimizes inference inside a fabric the operator owns. PagedAttention [32] raises throughput through memory management and batching, and the Virtual Token Counter (VTC) [33] adds fairness to that scheduler. All assume batch, token-count, and memory visibility inside the engine. Backpressure addresses the strictly upstream problem: fair admission before work reaches such a fabric, most commonly an unmodifiable third-party API. e) Workflow engines and HTTP retry gateways: Engineinternal advances [15]–[17] do not change where admission against an external cap must run. HTTP retry gateways [4] centralize routing and retries at a layer that cannot release a worker slot. These gateways compose cleanly with Backpressure for routing and key management. VIII. D ISCUSSION AND L IMITATIONS With Backpressure, a cap the operator cannot change can still be scheduled fairly, as the waiting happens outside the worker slot. Neither the fairness rule nor the deferral depends on how admission state is stored or which engine hosts the wait. The caps must be static and known (A1 to A3), which bounds where the approach applies. Adapting to providerreported or drifting limits is not covered. Client-side probing

in the Additive Increase Multiplicative Decrease (AIMD) tradition [34] is a natural starting point. We evaluate only on Temporal, but other engines should behave similarly, as the approach needs only a durable sleep, which most of them offer [12]–[14]. The synthetic upstream reproduces published 429 semantics but not every detail of a live endpoint, which we argue suffices to evaluate our prototype. Admission is serialized by one authoritative copy of the shared state. We do not benchmark its ceiling or sharding by target; at the measured admission latency, one primary serializes far more admissions per second than current provider caps allow. IX. C ONCLUSION Workflow engines assume elastic downstream services, and none of them links an external cap to the work it dispatches. LLM providers make that gap a daily operational problem. Their caps are hard, owned by a third party, and binding on requests and tokens at once. Backpressure adds the link at the worker, the one place the operator still controls. Our gate lifts achievement-Jain from 0.60 to 0.89 on a cross-priority workload and cuts high-priority tail latency roughly eightfold. When tokens bind, it holds dominant-resource fairness near 0.99. As more applications depend on scarce third-party APIs, we believe workflow engines should offer such admission control as a built-in feature. ACKNOWLEDGEMENT OF G ENERATIVE AI U SE Generative AI assistants (Anthropic Claude, OpenAI ChatGPT) supported an initial broad survey of related work and provided reviews of drafts. All citations were read and verified by the authors, who take full responsibility for all content. R EFERENCES [1] OpenAI. (2026) Rate limits in the OpenAI API. [Online]. Available: https://developers.openai.com/api/docs/guides/rate-limits [2] Anthropic. (2026) Anthropic API: Rate limits. [Online]. Available: https://platform.claude.com/docs/en/api/rate-limits [3] Microsoft. (2026) Azure OpenAI quotas and limits. [Online]. Available: https://learn.microsoft.com/en-us/azure/foundry/openai/quotas-limits [4] BerriAI. (2026) LiteLLM. [Online]. Available: https://github.com/ BerriAI/litellm [5] Portkey AI. (2026) Portkey AI Gateway. [Online]. Available: https://portkey.ai [6] Helicone. (2026) Helicone. [Online]. Available: https://helicone.ai [7] Kong Inc. (2026) Kong AI Gateway. [Online]. Available: https: //konghq.com/products/kong-ai-gateway [8] A. Demers, S. Keshav, and S. Shenker, “Analysis and simulation of a fair queueing algorithm,” SIGCOMM Comput. Commun. Rev., vol. 19, no. 4, pp. 1–12, 1989. [9] M. Shreedhar and G. Varghese, “Efficient fair queuing using deficit round-robin,” IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375–385, 1996. [10] Temporal Technologies. (2026) Temporal. [Online]. Available: https: //temporal.io

[11] R. K. Jain, D.-M. W. Chiu, and W. R. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” Digital Equipment Corp., Tech. Rep. DEC-TR-301, 1984. [12] Amazon Web Services. (2026) AWS Step Functions. [Online]. Available: https://aws.amazon.com/step-functions/ [13] Microsoft. (2026) Azure Durable Functions. [Online]. Available: https://learn.microsoft.com/en-us/azure/durable-task/ durable-functions/durable-functions-overview [14] Apache Software Foundation. (2026) Apache airflow. [Online]. Available: https://airflow.apache.org [15] S. Zhuang, S. Wang, E. Liang, Y. Cheng, and I. Stoica, “ExoFlow: A universal workflow system for Exactly-Once DAGs,” in Proc. USENIX OSDI, 2023, pp. 269–286. [16] S. Burckhardt et al., “Netherite: efficient execution of serverless workflows,” Proc. VLDB Endow., vol. 15, no. 8, pp. 1591–1604, 2022. [17] Z. Jia and E. Witchel, “Boki: Stateful serverless computing with shared logs,” in Proc. ACM SOSP, 2021, pp. 691–707. [18] N. Bronson, A. Aghayev, A. Charapko, and T. Zhu, “Metastable failures in distributed systems,” in Proc. HotOS, 2021, pp. 221–227. [19] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant resource fairness: Fair allocation of multiple resource types,” in Proc. USENIX NSDI, 2011, pp. 323–336. [20] Linux Foundation. (2026) Valkey. [Online]. Available: https://valkey.io [21] M. Welsh, D. Culler, and E. Brewer, “SEDA: an architecture for well-conditioned, scalable internet services,” SIGOPS Oper. Syst. Rev., vol. 35, no. 5, pp. 230–243, 2001. [22] I. Cho, A. Saeed, J. Fried, S. J. Park, M. Alizadeh, and A. Belay, “Overload control for µs-scale RPCs with Breakwater,” in Proc. USENIX OSDI, 2020, pp. 299–314. [23] A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: the single-node case,” IEEE/ACM Trans. Netw., vol. 1, no. 3, pp. 344–357, 1993. [24] B. Raghavan, K. Vishwanath, S. Ramabhadran, K. Yocum, and A. C. Snoeren, “Cloud control with distributed rate limiting,” SIGCOMM Comput. Commun. Rev., vol. 37, no. 4, pp. 337–348, 2007. [25] A. Shieh, S. Kandula, A. Greenberg, C. Kim, and B. Saha, “Sharing the data center network,” in Proc. USENIX NSDI, 2011, pp. 309–322. [26] J. Visser and R. Szopa. (2016) Doorman: Global distributed client-side rate limiting. [Online]. Available: https://github.com/youtube/doorman/ blob/master/doc/design.md [27] S. DeDeo. (2021) Coordinated rate limiting in microservices. [Online]. Available: https://engineering.salesforce.com/ coordinated-rate-limiting-in-microservices-bb8861126beb/ [28] Reactive Streams. (2022) Reactive streams specification for the JVM. [Online]. Available: https://www.reactive-streams.org/ [29] Apache Software Foundation. (2019) A deep-dive into Flink’s network stack. [Online]. Available: https://flink.apache.org/2019/06/05/ a-deep-dive-into-flinks-network-stack/ [30] V. Sreekanti et al., “Cloudburst: stateful functions-as-a-service,” Proc. VLDB Endow., vol. 13, no. 12, pp. 2438–2452, 2020. [31] W. Zhang, V. Fang, A. Panda, and S. Shenker, “Kappa: a programming framework for serverless computing,” in Proc. ACM SoCC, 2020, pp. 328–343. [32] W. Kwon et al., “Efficient memory management for large language model serving with PagedAttention,” in Proc. ACM SOSP, 2023, pp. 611–626. [33] Y. Sheng et al., “Fairness in serving large language models,” in Proc. USENIX OSDI, 2024, pp. 965–988. [34] D.-M. Chiu and R. Jain, “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks,” Comput. Netw. ISDN Syst., vol. 17, no. 1, pp. 1–14, 1989.

Related documents

• Can Agent Harnesses and Inference Engines Hear Each Other? The HEAR Protocol for Agentic LLM Serving#1215694
• Can Agent Harnesses and Inference Engines Hear Each Other? The HEAR Protocol for Agentic LLM Serving#1194480
• Typed Federated Artifacts for the Agentic Web:Sharing Tool-Routing Knowledge Across Frozen,Heterogeneous LLM Agents#974902
• Substrate-Portable Execution for Production LLM Workflows#973734
• Evaluating LLMs as Agentic Workflow Executors in Real-World Customer Support Skills#1324947