Source-linked AI summary
Kafila: Serving Large Language Models on a Trusted Set of Heterogeneous Commodity Machines
Murtaza Rangwala, Richard O. Sinnott, Rajkumar Buyya
TL;DR
A trusted group may collectively have enough memory to run an LLM, even when no single member’s device can, but open swarms do not meet its membership constraint. Kafila forms a ring and plans model placement for those heterogeneous devices; across three fleets, it shortens the slowest stage against standard divisions and improves throughput on a shared LAN.
Problem
A bounded trusted group may have enough combined memory for an LLM, but unlike an open swarm it must use every admitted device and cannot route around a slow one.
Source: §I · p. 1Method
Kafila forms a ring behind NATs and plans block assignment and head placement from measured device capability and reachability.
Source: §I · p. 2, §III · p. 4Results
Kafila’s bottleneck stage is up to 5.2× shorter than uniform division and up to 3.0× shorter than a memory-proportional one.
Source: B. Dividing the model · p. 8Takeaways & Limitations
On a shared LAN, Kafila’s division delivers 1.56× the throughput of a uniform split and 1.25× of a memory-proportional one.
Source: B. Dividing the model · p. 8Reachability prediction is a prior, not a guarantee; predicted-direct edges can fail verification and fall back to relaying.
Source: A. Bootstrap and reachability discovery · p. 4
Abstract
from arXiv · showhide
Between them, the members of a research group or a circle of friends own several consumer computers, none large enough to run a capable large language model. Existing systems pool such capacity across open swarms anyone may join, which a group admitting only trusted machines cannot use. Bounding membership removes what they depend on: a swarm holds each part of the model on several peers and routes around a slow one. A bounded session must use every device it admits. Its pipeline advances at the pace of whichever device received a share it cannot serve quickly, so the division has to be right before serving begins. We propose Kafila, whose protocol assembles a ring from behind NATs, preferring direct paths and relaying where traversal fails, while its planner measures each device's memory bandwidth, capacity and reachability, divides the model exactly for a fixed ring order, and places the head, which holds the embedding and output projection, together with that division rather than beforehand. On machines with different capabilities across three fleets, from a shared LAN to five devices spanning two continents, Kafila shortens the slowest pipeline stage by up to $5.2\times$ against the even split of pipeline parallelism, as in GPipe, and up to $3\times$ against the memory-proportional split of personal-device inference, as in exo, keeps 75 to 87 per cent of the committed hardware doing work where those divisions fall below half, and serves a model no uniform split can place on the fleet at all. What that is worth to a user depends on how much of a token is computation rather than network. Where the members share a network the same division returns $1.56\times$ the throughput of a uniform split and $1.25\times$ of a memory-proportional one, and under four concurrent users that lead compounds to $3.2\times$ rather than fading, each user served at almost the rate of one.
I. INTRODUCTION
Groups may collectively own enough hardware to run a capable LLM even when no single device can, but open swarms are unsuitable for users who restrict participation to trusted machines. Kafila forms a bounded session and plans a model division for its heterogeneous devices, which must all participate.
I. INTRODUCTION
- A competitive model may fit the group’s combined memory even when it cannot fit on any one member’s device.Turning that aggregate capacity into a usable model server is a device-to-device coordination problem.Source: §I · p. 1
- Open swarms can pool small machines, but their open membership makes them unsuitable for users who want to run models only on trusted machines.Their redundancy also lets them route around slow peers, an option a bounded session lacks.Source: §I · p. 1
- A bounded session must use every admitted device, so a pipeline’s slowest stage determines its pace and the model division must suit the devices before serving begins.Unlike an open swarm, the session has no redundant peers to route around a slow participant.Source: §I · pp. 1–2
- Kafila’s protocol forms a pipeline behind NATs without router configuration, preferring direct paths and relaying only when traversal fails.The rendezvous service is used for signaling.Source: §I · p. 2
- Kafila’s planner uses measured device capabilities to assign model blocks and place the head, while solving placement jointly with the division for a fixed ring order.Across three fleets, it shortens the slowest stage by up to 5.2× where capability-blind divisions leave hardware idle, and serves a model no uniform split can place.Source: §I · p. 2
II. RELATED WORK
Prior collaborative inference systems either rely on open, redundant populations or use partitioning assumptions that do not fit bounded, heterogeneous sessions. Kafila instead plans for fixed membership and measured reachability, with a fixed ring order enabling exact block placement.
A. Open-swarm collaborative inference
- Open swarms route around slow or departing peers using redundant blocks, but a bounded trusted group lacks spare peers and must rely on its initial division.Runtime routing and scheduling suit changing open populations, not small sessions with fixed membership.Source: A. Open-swarm collaborative inference · p. 2
B. Pipeline parallelism over heterogeneous, imperfectly connected machines
- GPipe assigns equal layer counts and exo assigns shares by memory, assumptions that fail when device memory and reading speed do not rank alike.The resulting divisions can give a device more work than it can serve at the assumed rate.Source: B. Pipeline parallelism over… · p. 2
- PipeDream, PipeEdge, and PipePar minimize the slowest stage or extend that objective to unequal devices, but assume complete connectivity and an administratively managed deployment.Kafila must choose ring order from measured reachability, and jointly place the head because its embedding and output projection make it asymmetric.Source: B. Pipeline parallelism over… · p. 2
- Kafila fixes ring order from measured reachability, then solves block placement exactly using chain-on-chain partitioning.The cited result makes fixed-order partitioning polynomial-time solvable, while choosing the order as part of the same problem is NP-complete.Source: B. Pipeline parallelism over… · pp. 2–3
C. NAT traversal
Kafila targets sessions whose members may be separated by NATs and unevenly connected, while also differing in memory and bandwidth. Its model uses a ring for inference and a separate rendezvous service for signaling and NAT traversal.
C. NAT traversal
- Hole punching is an assumption to verify for a session’s small, idiosyncratic membership, rather than a connectivity rate to inherit from measurements across arbitrary peers.A cited study reports roughly 70% success after relay reservation and address discovery across more than 85,000 IPFS networks.Source: C. NAT traversal · p. 3
D. Summary
- A session has neither a spare peer nor an administrator, so its model division is decided in advance from device capabilities and reachability.Kafila must order members by measured reachability, a step a cluster does not need.Source: D. Summary · p. 3
III. THE KAFILA SESSION MODEL
- The rendezvous handles registration and NAT-traversal signaling, holds no model weights, and performs no inference; the host selects the model and other participants join as members.The rendezvous carries activations only as an explicit last-resort fallback, and then only as ciphertext.Source: §III · p. 3
- The planner chooses which member holds the head because its embedding, unembedding, and sampler are additional to that member’s block allocation.Head placement and block division constrain each other and are solved together.Source: §III · p. 3
- A token passes from the head through each member’s block range and returns to the head, while each member’s compute overlaps the next member’s transfer.Edge cost depends on whether adjacent members can connect directly, so ring ordering and block assignment are planner responsibilities.Source: §III · pp. 3–4, Figure 1 · p. 4
IV. PROTOCOL: FORMING A SESSION FROM BEHIND NAT
Kafila forms a session without requiring inbound connections or router configuration. It predicts reachability from per-device measurements, verifies only the chosen ring edges, and tolerates prediction errors through relay fallback.
IV. PROTOCOL: FORMING A SESSION FROM BEHIND NAT
- No participant must accept an unsolicited inbound connection or configure a router, avoiding the requirements of a host-listening-port design.The constraint governs the session-formation protocol.Source: §IV · p. 4
A. Bootstrap and reachability discovery
- The host registers a model identifier, expected member count, and capability over an outbound rendezvous connection, then receives a session code.Members connect outbound with that code, and the rendezvous exchanges candidate addresses.Source: A. Bootstrap and reachability discovery · p. 4
- Kafila classifies each member’s reachability against the rendezvous and STUN servers, avoiding direct probes of every member pair.Direct pairwise probing would require O(m^2) network operations.Source: A. Bootstrap and reachability discovery · p. 4
- Per-node NAT measurements predict pair feasibility with O(m^2) arithmetic and no packets, after O(m) probes classify members.Only the edges selected for the ring are then verified, using O(m) probes.Source: A. Bootstrap and reachability discovery · p. 4
- The quadratic prediction step is a table lookup, so network probing cost is linear in membership size at both ends.Source: A. Bootstrap and reachability discovery · p. 4
- Reachability prediction is a prior, not a guarantee; a predicted-direct edge that fails verification falls back to relaying.A predicted-relayed edge that connects directly can run faster than planned, and the predicted ring order is retained.Source: A. Bootstrap and reachability discovery · p. 4
B. Traversal and relay fallback
Kafila first attempts direct hole-punched paths and relays only when traversal fails. Its planner accounts for compute and network latency on every token, making both path cost and ring size relevant to serving time.
B. Traversal and relay fallback
- Kafila attempts a hole-punched direct path for every edge and relays through the rendezvous only when traversal fails.The data plane uses QUIC over UDP.Source: B. Traversal and relay fallback · p. 4
- A direct edge costs the members’ round trip between them, while a relayed edge costs the sum of their round trips to the rendezvous.The planner prices both cases in the same unit when ordering the ring.Source: B. Traversal and relay fallback · p. 4
- On relayed edges, the rendezvous forwards end-to-end encrypted datagrams and sees ciphertext, while direct edges keep even that traffic off the rendezvous.The rendezvous still knows session membership and member addresses through signaling.Source: B. Traversal and relay fallback · pp. 4–5
V. PLANNER: COST, PLACEMENT, ORDERING, AND ADMISSION
- Per-token circuit time sums each member’s compute stage and every ring-edge latency, so each additional member adds a hop paid on every token.The compute term subdivides fixed forward-pass work, while the latency term grows linearly with ring size.Source: §V · p. 5
A. Cost model
Kafila derives per-device stage costs from measured memory bandwidth and model sizes, accounting for the head’s additional memory and capacity requirements. It orders the ring using measured reachability costs, with a tie-break for the case where all edges must relay.
A. Cost model
- At batch size one, a stage reads each weight once and performs two floating-point operations per weight, making memory bandwidth the dominant cost.The cost model is derived rather than fitted to observed stage times.Source: A. Cost model · p. 5
- The head’s embedding and unembedding increase its per-token cost and resident memory, so head placement affects both stage cost and the number of blocks it can hold.The planner solves head placement together with block division.Source: A. Cost model · p. 5
B. Ring ordering
- An all-direct ring exists if and only if permissive members are at least as numerous as restrictive members; alternating them around the anchor achieves one when possible.The planner’s first ordering pass uses NAT behavior classes and a linear-time counting argument.Source: B. Ring ordering · p. 5
- When members have measured rendezvous round trips, the planner prices relayed edges at rA + rB and direct edges at the lower bound |rA − rB|, then searches ring orderings for the cheapest.Counting relayed edges alone is insufficient when a session spans multiple sites, where relay costs vary.Source: B. Ring ordering · p. 5
- When every edge must relay, all ring orders have the same relay cost, so Kafila breaks ties by placing members with similar rendezvous distances next to each other.This tie-break does not distinguish between equally relay-bound arrangements, but avoids choosing the worse of them when predicted-relayed edges connect directly.Source: B. Ring ordering · p. 5
C. Block placement
For a fixed ring order, Kafila solves block placement exactly as a chain-on-chain partition, then compares rotations to place the head. Its parametric search finds the smallest feasible bottleneck under device block limits.
C. Block placement
- Fixing the ring order makes block placement a chain-on-chain partition solvable exactly in polynomial time, unlike jointly choosing order and placement, which is NP-complete.The transformer blocks are contiguous and assigned across processors in their fixed order.Source: C. Block placement · p. 6
- The optimal bottleneck lies among at most O(k · m) candidate stage costs, which PARTITION sorts and binary-searches for the smallest feasible bound.Its left-to-right feasibility pass assigns the largest block count each device can hold while reserving at least one block for each remaining device; overall complexity is O(km log km).Source: C. Block placement · p. 6
- Kafila tests each of the m ring rotations with an exact partition solve and keeps the rotation with the lowest achieved bottleneck.The selected block counts are un-rotated to the original device order.Source: C. Block placement · p. 6
- To avoid choosing a head based on overhead differences smaller than measurement noise, Kafila keeps the anchor unless another rotation improves the bottleneck by more than margin μ = 0.05.Overhead is at most 2.2% of a measured stage, and run-to-run variation shifts a stage by at most 1.1%.Source: C. Block placement · p. 6
D. Admission
Kafila degrades through measurement tiers when devices lack inputs needed by the full cost model. After producing a division, it checks whether every device can hold its assigned model state at the session’s declared context and concurrency, rejecting plans that exceed available memory.
D. Admission
- When measurements are missing, Kafila uses full cost modeling if available, raw arithmetic throughput if not, and working-set proportions only when nothing is measured.The lower tiers omit information needed for head placement and are less informed divisions.Source: D. Admission · pp. 6–7
- After producing a division, Kafila checks each member’s available room at the declared context and concurrency and rejects assignments that exceed it.The rejection identifies the undersized device rather than reporting only that the session cannot run.Source: D. Admission · p. 7
- Admission establishes that a division fits the members’ collective memory, not that its resulting circuit time is worth serving.If the full cost model has tried every bottleneck-minimizing division and none fits, memory is the remaining reason to refuse.Source: D. Admission · p. 7
VI. IMPLEMENTATION AND EXPERIMENTAL SETUP
Kafila adapts a local-inference server to run sessions across Apple and Nvidia hardware. Its lightweight rendezvous and instrumentation support shard-level model fetching and per-stage performance measurement.
VI. IMPLEMENTATION AND EXPERIMENTAL SETUP
- Kafila forks Ollama and retargets it to MLX, allowing the same session and planner code to run across Apple silicon and Nvidia hardware.The implementation uses MLX’s Metal and CUDA backends.Source: §VI · p. 7
- Members fetch only their assigned weight shards by byte range, and replanning after a partial fetch costs little because checkpoint shards share tensors.Source: §VI · p. 7
- The rendezvous runs as an unprivileged service on a two-core cloud instance without an inference runtime or accelerator.Source: §VI · p. 7
- Session traces record predicted and measured costs, circuit time, and bytes per stage and hop; reported measurements use the median of four generations after a discarded cold generation.Time-to-first-token is separated into prefill and decode.Source: §VI · p. 7
A. Testbed and NAT emulation
Kafila is evaluated on heterogeneous fleets and on real and emulated NAT behavior. The results show that its reachability rule favors safe relay predictions, while measured paths connect directly when traversal succeeds and relay when it does not.
A. Testbed and NAT emulation
- The testbed varied network overhead from 12% on a shared LAN to 94% across continents, with three fleets whose device memory and speed rankings differed.Across fleets, bandwidth spanned an 11× range and memory a 4× range; home uplinks, intermittency, and churn were outside scope.Source: A. Testbed and NAT emulation · p. 7
VII. PERFORMANCE EVALUATION
- Planner comparisons used five independent sessions per cell, with uniform GPipe-style block counts and exo-style memory-proportional shares as baselines.The protocol was evaluated separately on real consumer connections and with NAT emulation for uncommon NAT-class pairs.Source: §VII · p. 7
A. Forming a session across real NATs
- On real networks, all US Central ring edges punched direct over public addresses at a median of 1.29 s, while LAN edges connected locally at 1.26 s.The LAN reachability rule predicted relays, but no edge needed the rendezvous.Source: A. Forming a session across real NATs · pp. 7–8
- On the intercontinental fleet, only the two co-located members connected directly; the other four ring edges relayed at a median of 20.8 s, carrying roughly four fifths of activation bytes as ciphertext.The ring ordering was optimal in predicted relayed edges and was verified against exhaustive search.Source: A. Forming a session across real NATs · p. 8
- 7 of 9 ordered NAT-class pairs matched the reachability rule’s prediction, and both errors predicted a relay where traversal succeeded directly.Table III reports the nine ordered pairs; neither error predicted a direct path when traversal would fail.Source: A. Forming a session across real NATs · p. 8, Table III · p. 8
B. Dividing the model
Kafila’s measured-capability division reduces the slowest pipeline stage across heterogeneous fleets, while its user-throughput advantage depends on network overhead. Joint head placement also lets it serve a model that a uniform split cannot fit.
B. Dividing the model
- Up to 5.2× shorter than uniform division and 3.0× shorter than memory-proportional division, Kafila’s bottleneck stage leaves 75–87% utilization where the heuristics fall below half.Table IV compares the divisions; Kafila’s stage imbalance is 1.4–1.8×, versus 2.1–5.5× for memory-proportional and up to 10.6× for uniform division.Source: B. Dividing the model · p. 8, Table IV · p. 8
- No uniform split of Qwen3-32b fits the intercontinental fleet’s 18 GB laptop after cache is reserved for four concurrent requests, but Kafila’s uneven division serves the model.The LAN fleet’s 12 GB member likewise bounds Qwen3-14b, so that fleet is evaluated on Qwen3-8b.Source: B. Dividing the model · p. 8
- On the LAN, Kafila delivers 1.56× the throughput of a uniform split and 1.25× that of a memory-proportional split, with non-overlapping five-session ranges.On the intercontinental fleet, the allocations’ served rates are within the five-session spread despite differences in bottleneck and utilization.Source: B. Dividing the model · p. 8
- Figure 2 shows four-user throughput gain over one user against network overhead; only Kafila’s balanced division scales near-linearly at every overhead.The imbalanced divisions drop away as overhead falls; points are per-fleet medians across models.Source: Figure 2 · p. 9
- Pinning the head at session opening or ordering by relay count rather than cost leaves the served division, bottleneck, and throughput within run-to-run variance on these fleets.The ablations matter elsewhere: an oversized head can make a session infeasible, and cost-blind ordering can relay unnecessarily; the cost model predicts per-stage compute to a median of 18% across 165 stages.Source: B. Dividing the model · p. 9
C. Serving several users at once
With little LAN network idle, the planner’s throughput lead grows under four users; across distant fleets, network overhead masks division differences. Bounded sessions trade swarm redundancy for membership, capability, and connectivity known before serving.
C. Serving several users at once
- At 12% network overhead, planner throughput rises 4.0×; memory-proportional and uniform divisions reach 2.5× and 2.0×, and its lead over uniform widens to 3.2× under four users.Imbalanced divisions stall at their overloaded stage, while the balanced division has headroom for four requests.Source: C. Serving several users at once · p. 9
- The LAN lead doubles under four users because the overloaded stage remains binding as batching shifts both weight streaming and computation.The division that unburdens the stage for one request is the one that scales to four.Source: C. Serving several users at once · p. 9
- Across US Central and intercontinental fleets, four-user throughput scales 3.9–4.0× and 3.5–4.0× respectively across divisions, with gains converging as network overhead rises.On US Central, the planner leads in absolute throughput at every size but the largest, where it ties; intercontinental results fall within session spread.Source: C. Serving several users at once · p. 9
VIII. CONCLUSIONS AND FUTURE WORK
- Across three fleets, the planner shortens the slowest stage by up to 5.2× versus uniform division and 3.0× versus memory-proportional division, keeping 75–87% of committed hardware working where alternatives fall below half.The planner also serves a model that uniform division cannot place on the fleet.Source: §VIII · p. 9
- Sessions trade swarm redundancy for membership, capability, and connectivity known before serving; future work includes cache recovery for changing membership and replanning for mobile members.Sharing cache reserved for prompts that never arrive is another proposed direction.Source: §VIII · pp. 9–10