Problem · How it works · Benchmarks · Quickstart · Architecture · Decisions

---

The problem

GPUs are the most expensive compute you will ever rent, and almost nobody uses them well.

Inference service time is affine, not linear, in batch size: a fixed kernel-launch and weight-paging cost, plus a marginal per-token cost. On a typical 8B-parameter decoder that is roughly 18ms + 0.022ms × tokens. Serve one request at a time and a 200-token completion burns 80% of its GPU time on overhead you paid for and threw away.

So you batch. And immediately hit the wall every inference platform hits:

Waiting to fill a batch recovers throughput but adds queueing delay. A fixed batch size stalls forever under light traffic. A fixed timeout is a number that is correct at exactly one arrival rate and wrong at every other.

Then the harder problems arrive. Your replicas are not identical — different hardware generations, different KV-cache residency, noisy neighbours. One of them starts OOM-ing and fails in 2ms, so your latency-aware load balancer sends it more traffic. Traffic doubles and your static concurrency cap is suddenly either throttling a healthy fleet or letting queues grow until every request times out. And you still need to ship a new model version without betting the entire user base on it.

Halcyon is a control plane that treats all four as one scheduling problem.

	Naive approach	What Halcyon does
Batching	Fixed size, or a tuned timeout	Earliest-deadline-first with an online cost model. Batch size is emergent, and requests that provably cannot be served in time are shed in microseconds
Routing	Round-robin or least-connections	Peak-EWMA scoring under power-of-two-choices, with outcome-based circuit breaking and p95-triggered hedging
Admission	Static concurrency cap	Gradient-based adaptive limiter that infers queueing from latency, plus per-tenant token buckets and priority-graded shedding
Rollout	Deploy and watch a dashboard	Sticky-hash traffic splitting with an SLO-gated canary controller that promotes or rolls back on evidence

---

The numbers

Measured with a fully seeded, reproducible discrete-event simulation — same arrival trace, same device model, three schedulers. Run it yourself: npm run bench.

Workload: Poisson arrivals, log-normal request sizes, mixed SLOs (30% urgent at 120ms, 70% relaxed at 900ms), single accelerator at 18ms + 0.022ms/token, 120s simulated.

Goodput counts only requests completed within their deadline, as a share of requests offered — so a scheduler cannot score well by refusing hard work.

At saturation — 200 req/s

strategy	goodput/s	p50	p95	urgent SLO	util
no batching	0.3	11544ms	11736ms	0.0%	100%
fixed batch (32 / 25ms)	155.7	158ms	300ms	27.9%	99.5%
halcyon	163.6	130ms	237ms	41.0%	99.3%

Past saturation — 260 req/s, against a ~219 req/s ceiling

strategy	goodput/s	p50	p95	relaxed SLO
no batching	0.3	11576ms	11704ms	0.1%
fixed batch (32 / 25ms)	5.2	2398ms	2618ms	2.8%
halcyon	83.1 ⟶ 16×	885ms	1020ms	45.1%

Nothing can serve this trace in full. The only question is which requests a scheduler sacrifices — and a scheduler that admits work it cannot finish sacrifices all of them.

Below saturation, Halcyon and fixed batching are indistinguishable. That is the honest result, and it is reported here rather than hidden: deadline-awareness earns nothing when there is slack for everyone. It earns everything at the edge, which is where systems break.

Verified on a live fleet, not just in simulation

$ node scripts/loadtest.mjs --clients 32 --seconds 20
  requests        4706       success rate    100.00%
  throughput      233.8 req/s
  p50/p95/p99     128 / 185 / 235 ms
  mean batch size 12.44

$ node scripts/verify-rollout.mjs
  [2s]  progressing at 25%      25%  -> advance   | baseline p95 168ms, canary p95 63ms
  [6s]  progressing at 100%     100% -> promote   | baseline p95  71ms, canary p95 75ms
  PASS: rollout promoted and v2 now serves 100% of traffic.

Both run in CI on every push, against a real fleet — not as illustrations.

And it catches a regression nobody wrote a test for

Running the same fleet under sustained load (18,036 requests, 0 errors, 0 shed) with a canary ramping behind it produced this decision trail, unprompted:

  25% -> hold      insufficient_data      | baseline 5398 req p95 159ms | canary   16 req p95  85ms
  25% -> hold      awaiting_confirmation  | baseline 1647 req p95 142ms | canary  488 req p95  68ms
  25% -> advance                          | baseline 1595 req p95 148ms | canary  500 req p95  63ms
  60% -> hold      awaiting_confirmation  | baseline  462 req p95  86ms | canary 1756 req p95 108ms
  60% -> rollback  latency                | baseline  440 req p95  77ms | canary 1680 req p95 121ms

At 25% the canary looked twice as fast as the baseline — it runs on the faster accelerator. At 60% it regressed and was rolled back, because one canary replica was carrying 60% of traffic while two baseline replicas shared the remaining 40%. The canary was never slower; it was under-provisioned, and that only becomes visible under load.

A rollout validated at 1% and then promoted would have shipped it. This is the entire argument for ramping progressively and judging against a concurrent baseline.

---

Quickstart

git clone https://github.com/NavyashreeNS/halcyon.git
cd halcyon
npm install
npm run build

# Gateway + a deliberately heterogeneous fleet (one fast replica, one 0.6x straggler,
# one on a second model version). Identical replicas make any load balancer look good.
node scripts/dev-stack.mjs --canary

Then, in another terminal:

# Send one request
curl -s localhost:8080/v1/infer \
  -H 'x-api-key: demo-key-premium' -H 'content-type: application/json' \
  -d '{"model":"llama-3-8b","input":"hello","deadlineMs":2000,"maxOutputTokens":64}' | jq

# Drive real load
node scripts/loadtest.mjs --clients 32 --seconds 20

# Start a canary and watch it promote itself on measured evidence
node scripts/verify-rollout.mjs

Dashboard	npm run dev --workspace @halcyon/web → http://localhost:3000
Live state	http://localhost:8080/v1/control/state
Prometheus	http://localhost:8080/metrics
Benchmark	npm run bench
Full stack	npm run stack:up (Postgres, gateway, 3 workers, dashboard, Prometheus, OTel collector)

The response tells you what the scheduler decided, not just what the model said:

{
  "version": "v1",
  "replicaId": "replica-b",
  "hedged": false,
  "timings": { "queuedMs": 4, "executionMs": 118, "totalMs": 122 },
  "batch": { "size": 17, "reason": "deadline" }
}

"reason": "deadline" means this batch was flushed early because waiting one more millisecond would have breached someone's SLO. That is the scheduler explaining itself.

---

How it works

A request passes through four decisions, in an order that is not arbitrary.

flowchart LR
    C([client]) --> A

    subgraph GW["gateway"]
        direction TB
        A["<b>1 · admission</b><br/>token bucket → adaptive limit"]
        R["<b>2 · rollout</b><br/>hash sessionKey → version"]
        B["<b>3 · batching</b><br/>EDF + deadline feasibility"]
        T["<b>4 · routing</b><br/>peak-EWMA P2C + hedge"]
        A --> R --> B --> T
    end

    T --> W1["replica a<br/><i>v1 · a10g</i>"]
    T --> W2["replica b<br/><i>v1 · a10g</i>"]
    T --> W3["replica c<br/><i>v2 · h100</i>"]

    W1 & W2 & W3 -.->|"latency, errors"| C2["canary controller"]
    C2 -.->|"advance / rollback"| R
    W1 & W2 & W3 -.->|"observed batch cost"| B

    A -.->|429 quota / 503 overload| X([shed])
    B -.->|503 deadline unreachable| X

    style GW fill:#0d1117,stroke:#2a3644,color:#e6edf3
    style X fill:#2d1214,stroke:#f85149,color:#f85149
    style C2 fill:#1a1226,stroke:#bc8cff,color:#bc8cff

Loading

Admission is first because every later step costs real resources, and a rejected request should cost none. Version resolution precedes batching because requests for different versions cannot share a batch — they are different weights on different replicas. Routing comes last because the load estimate needs to know how big the batch is.

1 · Deadline-aware continuous batching — packages/core/src/batching/

Requests carry an absolute deadline and are ordered earliest-deadline-first. On every arrival and timer expiry the scheduler asks one question:

slack = earliestDeadline − now − predictedCost(queuedTokens) − safetyMargin − inFlightWork

Positive slack, the batch keeps growing. Non-positive, flush now — however small the batch. A lingerMs ceiling bounds waiting when every deadline is generous.

predictedCost comes from a recursive least-squares fit with exponential forgetting of serviceTime ≈ intercept + slope × tokens, updated from every executed batch. Forgetting matters: the same model behaves differently after a driver upgrade or a co-tenant landing on the device, and a fit with unbounded memory takes hours to notice.

Two lanes — interactive and bulk — keep a nightly embedding backfill from competing with a user-facing completion, with bulk work aged into the fast lane so it cannot starve.

The part that produces the 16×: because the scheduler can estimate cost, it can also prove when a request is infeasible — accounting for work queued ahead of it under EDF and work already dispatched to a device. Those requests are rejected in microseconds instead of consuming a GPU slot and returning a response nobody is still waiting for.

2 · Peak-EWMA routing under power-of-two-choices — packages/core/src/routing/

score = (inflight + 1) × ewmaLatency / weight

An estimate of the queueing delay a new request would face — Little's Law, per replica. The router samples two candidates at random and takes the better one.

Why not just pick the global minimum? Because every gateway instance would independently compute the same "best" replica and stampede it together, then stampede the next one. Two random choices provably reduces maximum load from Θ(log n / log log n) to Θ(log log n) and is immune to that resonance.

The EWMA decays by elapsed time, not sample count — a plain EWMA freezes at its last reading when a replica stops receiving traffic, making a shunned replica look permanently excellent.

Health is judged on outcomes, not timing, by a per-replica circuit breaker with exponential re-open backoff. This closes the black-hole failure mode: a replica failing in 2ms looks fast to a latency-based balancer, which then sends it more traffic.

Hedging fires at the fleet p95, bounding extra load at ~5% while racing only requests already behaving abnormally. The loser is aborted so it stops occupying an accelerator.

3 · Adaptive admission control — packages/core/src/admission/

You cannot know the right concurrency limit. It changes with model version, hardware, batch composition and neighbours — a number tuned in March is fiction by June.

So don't try. Detect queueing instead, which has an unmistakable signature: short-window latency rising above long-window latency.

g      = clamp(longRTT / shortRTT, 0.5, 1.0)     // < 1 exactly when a queue forms
target = limit × g + √limit                       // multiplicative decrease, sublinear increase

Same family of controller as TCP congestion control, for the same reason: neither endpoint can observe the bottleneck directly, so both infer it from delay.

Failed requests release their slot but are excluded from the RTT estimate — a fast failure otherwise reads as a latency improvement and would make the limiter raise the limit on a system that is falling over.

Per-tenant token buckets run before the fleet limit, so one customer's runaway retry loop is attributed to that customer instead of triggering fleet-wide shedding that punishes everyone else. Every Retry-After is computed from the actual refill time.

4 · SLO-gated progressive rollout — packages/core/src/rollout/

Traffic is assigned by hashing a stable key (session, user, conversation), not by a coin flip. Random assignment sends one user's requests to different model versions mid-conversation and turns every per-session metric into a blend of both arms — destroying the comparison the canary exists to make. Hashing gives stickiness with no shared state between gateways.

The canary is compared against the baseline running concurrently on the same fleet, never against history, which would confound the version change with time of day and traffic mix.

Three guards, each earning its place:

• Minimum request count — at 1% traffic a window may hold eight requests; two failures read as a 25% error rate.
• Relative and absolute error tolerance — against a flawless baseline, any error at all is an infinite relative regression.
• Consecutive streaks in both directions — one bad window is a blip, n in a row is a trend.

A data-sparse window touches neither streak: resetting the healthy one stalls low-traffic rollouts forever, resetting the unhealthy one lets a real regression hide behind quiet periods.

---

Architecture

halcyon/
├── packages/
│   ├── core/          ← the algorithms. pure, dependency-free, clock-injectable
│   │   ├── batching/    deadline-aware batcher + online cost model
│   │   ├── routing/     peak-EWMA P2C router + circuit breaker
│   │   ├── admission/   token bucket + gradient-based adaptive limiter
│   │   ├── rollout/     sticky traffic splitter + canary controller
│   │   ├── stats/       HDR-style latency histogram, time-decayed EWMA
│   │   ├── test/        103 deterministic tests — no sleeps, no I/O
│   │   └── bench/       seeded discrete-event simulation
│   ├── contracts/     Zod schemas — one definition, enforced at runtime and compile time
│   ├── telemetry/     Prometheus registry + W3C trace context + OTLP exporter
│   └── db/            Drizzle schema, migrations, typed queries
├── apps/
│   ├── gateway/       Fastify. composes the four algorithms into a request path
│   ├── worker/        model replica with a pluggable runtime interface
│   └── web/           Next.js 15 control-plane dashboard
├── infra/
│   ├── docker/        multi-stage images, compose stack, Prometheus rules, OTel config
│   ├── k8s/           Deployment + StatefulSet + HPA + PDB, hardened pod security
│   └── terraform/     VPC, RDS, ECR — the slow-moving layer only
└── docs/adr/          why each decision was made, and what it cost

packages/core has no dependencies and performs no I/O. No Date.now(), no globals — every time-dependent component takes an injectable Clock. That single constraint is why the entire scheduling and rollout surface is tested deterministically in under three seconds, and why the same code runs unchanged inside the gateway, inside a worker, or inside the simulation harness.

Engineering practices

• Strict TypeScript everywhere — noUncheckedIndexedAccess, exactOptionalPropertyTypes, verbatimModuleSyntax. No any, no non-null assertions on external data.
• Deterministic tests. Injectable clocks and seeded PRNGs. No sleep(), no flakes.
• Reproducible benchmarks. The simulation is fully seeded, so a change in the output is a change in behaviour rather than machine noise. CI posts it to the job summary.
• CI that can actually fail — format, typecheck, 159 tests, the benchmark, a real end-to-end load test against a booted fleet, an automated canary rollout verification, and a three-service Docker build matrix.
• Metrics with bounded cardinality. Every label has a small domain. Histogram buckets are exported, not pre-computed quantiles, because buckets aggregate across instances and quantiles do not.
• Security defaults: non-root containers, read-only root filesystems, all capabilities dropped, SHA-256 + constant-time API-key comparison, no secrets in Terraform outputs.

---

Design decisions

Each ADR records the alternatives considered and what the decision cost — including the bugs it caused.

	Decision	The interesting part
0001	Deadline-aware batching	Independently clamping the cost model's slope and intercept inflated the intercept to 6.9s, and the scheduler correctly rejected 4,889 servable requests. Fixed with constrained least squares
0002	Peak-EWMA P2C routing	Using the circuit breaker's tryAcquire as an eligibility filter leaked half-open probe slots to replicas that were never chosen, making recovery impossible
0003	Adaptive concurrency	Why fast failures must be excluded from the latency estimate, and why quota checks precede the fleet limit
0004	Sticky canary rollouts	Why Math.random() < weight is a correctness bug, not a style choice
0005	In-memory scheduling state	Instances disagreeing is the design, not a compromise — P2C requires it

Five bugs worth reading about

Each was found by running the system rather than by reading it, and each is now pinned by a regression test.

1. Backpressure scored as failure — which crashed the gateway. A worker executing a batch answers 503 immediately, and the gateway counted that against the replica's circuit breaker. So a replica was shunned for being fully utilised, which pushed its load onto the next replica, which was then shunned too. Under sustained load the fleet ate itself: No available replica, an error storm, and a hard process exit. Backpressure and faults are different signals — a busy replica is now retried elsewhere and its breaker untouched. The same run went from a crash to 18,036 requests, 0 errors, 0 shed.

   Its neighbour: hedging now stands down near saturation. A hedge spends spare capacity to buy tail latency, and when there is none to spend it occupies the very replica the next batch needed — turning a latency optimisation into a throughput regression exactly when the fleet can least afford one.

2. A queue requests could disappear into. With every replica draining there was nowhere to dispatch, so the batcher held its contents — forever. The caller's connection stayed open long past any useful answer. A scheduler that reasons about deadlines must also enforce them on its own queue: queued work is now evicted the moment its deadline passes, and the client gets an explicit deadline_unreachable instead of a hang.

3. A busy-spin at saturation. As load approaches capacity, deadline slack converges to zero from above. The scheduler armed a timer 0.4ms out, woke, recomputed an equally tiny slack, and re-armed — burning the event loop precisely when it was scarcest. No runtime honours a sub-millisecond timer anyway, so slack below one tick is slack that cannot be spent.

4. Promise.race in the hedge path. Race settles on the first promise to settle — including one that rejects. A hedge failing fast against a busy replica killed batches whose primary was running perfectly. Exactly the failure hedging exists to prevent. The semantics needed are Promise.any: succeed if any attempt succeeds, fail only if all do.

5. Scoring is not exclusion. Peak-EWMA makes a busy replica less attractive, but a worker that accepts one batch at a time needs it to be ineligible — a slow-enough replica could still win the comparison while already occupied. 2.7% of requests failed on arrival until the router gained a hard per-replica concurrency ceiling.

---

API

Method	Path	Purpose
POST	/v1/infer	Submit inference. Returns the scheduler's decisions alongside the output
POST	/v1/workers/register	Replica registration
POST	/v1/workers/:id/heartbeat · /drain	Liveness and graceful removal
GET	/v1/control/state	Complete control-plane state in one round trip
POST	/v1/control/rollouts	Begin a progressive rollout
POST	/v1/control/rollouts/:model/promote · /abort	Operator override
GET	/v1/control/rollouts/:model/history	Every canary decision with the metrics behind it
GET	/healthz · /readyz · /metrics	Liveness, readiness, Prometheus

Rejections are typed and actionable — quota_exceeded, overloaded, deadline_unreachable, queue_full — each with a computed Retry-After. A client can tell "you are over quota" from "the fleet cannot meet your deadline right now", and respond differently.

---

Scope

Built as a systems-engineering project, and honest about its edges:

• The model runtime is simulated — a calibrated device model behind a ModelRuntime interface, not a real GPU. Swapping in vLLM or TensorRT-LLM means writing one adapter; the interface exists so that substitution touches nothing else. The simulation is deliberate: it makes the whole system runnable on a laptop and lets failure modes be injected rather than waited for.
• Benchmark figures come from a seeded simulation with an explicit device model, stated above so they can be reproduced or disputed. The live-fleet numbers are from real HTTP against real processes.
• Per-tenant quotas are per-instance, so n gateways allow n× burst. Deliberate, and explained in ADR 0005 — quotas are fairness, the adaptive limiter is protection.

License

Apache 2.0 — see LICENSE.