proposal(scheduler): cross-dimensional resource balance scoring to prevent GPU fragmentation

[0x-auth]

What you would like to be added?

A cross-dimensional resource balance scoring plugin that detects and prevents resource fragmentation at scheduling time, rather than fixing it after the fact.

Currently KAI supports bin-packing (fill nodes fully) and spread (distribute evenly), but neither considers the shape of resource usage across dimensions. A node can be 95% on GPU-Memory but 15% on GPU-Compute — bin-packing sees it as "mostly full" and spread sees it as "partially used." Both are wrong. That node has stranded compute.

The proposed plugin scores nodes by measuring how much more balanced they become after placing a pod, using cosine alignment between the pod's request vector and the node's free capacity vector, combined with Shannon entropy reduction.

Why is this needed?

In GPU clusters running mixed inference workloads, resource fragmentation happens across dimensions, not just within them:

• Large model serving (LLaMA 70B, DeepSeek): VRAM full, GPU compute ~20% → compute is stranded
• Many small models (batch inference): GPU compute saturated, VRAM ~30% used → memory is stranded
• Mixed CPU+GPU nodes: CPU 90%, GPU 40% → GPU capacity wasted

This is the "jagged cluster" problem described in #1311, but caught at scheduling time instead of after the fact. Prevention > cure.

With the vectorized resource representation landing (#1353), adding a vector-based scoring plugin becomes natural — the infrastructure is already there.

Proposed approach

Score each node using a 6D resource vector [CPU, Memory, GPU-Compute, GPU-Memory, IOPS, Network]:

alignment     = cosine_similarity(pod_request, node_free_capacity)
exhaustion    = φ × entropy_reduction(node_before, node_after) + utilization_delta
leak_penalty  = 0.15 × count(stranded_dimensions)

score = φ × alignment + exhaustion - leak_penalty + headroom × 0.3

Where φ = 1.618 (golden ratio) provides parameter-free weighting — no per-cluster tuning needed.

Benchmark (synthetic, 50 nodes × 500 pods): 13% improvement in resource balance vs LeastAllocated, zero stranded nodes in 4/5 scenarios. Scoring latency: ~115ns/op, zero allocations.

This is already proposed as a Koordinator scheduler plugin (koordinator-sh/koordinator#2839). Open-source auditor that detects existing imbalance: github.com/0x-auth/lambda-g-auditor

Happy to contribute the implementation if there's interest. The scoring function is stateless and fits naturally into the existing GpuOrderFn plugin pattern.

[enoodle]

Hello @0x-auth
This is a very interesting proposal
Currently KAI-Scheduler doesn't support GPU compute requests, but this could be relevant to CPU, memory and GPU memory.
I suggest that you open a design PR with a link to this issue where you can describe the use case in more detail and also the proposed solution. For example elaborate on the score function and I would also be interested in comparing it's results to dominate resource strategies.

[0x-auth]

Hi @enoodle, design PR is up: #1374
It covers the score function in detail (worked numerical example included), and compares against BalancedAllocation DominantResource, LeastAllocated, and MostAllocated across 5 heterogeneous scenarios. Happy to discuss or adjust scope.

[Whatsonyourmind]

The scoring function design is mathematically sound. A few observations that might help the review.

Cosine similarity as a directional metric. Using cosine_similarity(pod_request, node_free_capacity) is a good choice because it is scale-invariant — a pod requesting [1 GPU, 4GB] gets the same alignment score as [2 GPU, 8GB] on the same node. This is the correct property for a tiebreaker.

However, cosine similarity has a known degeneracy in low dimensions: when one dimension dominates (a pod requests only GPU-Memory and zero CPU), the cosine depends entirely on the node's GPU-Memory component, ignoring other dimensions. This is actually desirable here — a GPU-only pod SHOULD be placed based on GPU availability.

Entropy as a balance metric. Shannon entropy H = -sum(p_i * log(p_i)) where p_i = used_i / total_i measures how evenly utilized a node is. Maximum entropy = all dimensions equally utilized = perfectly balanced. The entropy reduction H(before) - H(after) measures how much a placement improves balance. Clean formulation.

One subtle issue: entropy is undefined when any p_i = 0 or p_i = 1. In practice, handle these with p_i * log(p_i + epsilon) or by clamping to [epsilon, 1-epsilon].

On using phi (1.618) as a weight. The golden ratio as a "parameter-free" weight is not actually parameter-free — it is an arbitrary constant. It likely works in benchmarks because any constant in [1, 3] would produce similar results, since the alignment and exhaustion terms are already on similar scales. I would suggest either making it an explicit tunable with 1.618 as default, or providing theoretical justification for why phi is specifically optimal. Without such justification, the "parameter-free" claim may invite skepticism during review.

Comparison with DRF. The Dominant Resource Fairness strategy (YARN/Mesos) maximizes the minimum dominant resource share across users. Your scoring function optimizes a different objective — node-level balance rather than cross-pod fairness. These are complementary: DRF ensures fairness, Lambda-G ensures efficiency. The 23% improvement over BalancedAllocation makes sense because BalancedAllocation considers one dimension at a time, while your function considers all dimensions jointly via the cosine term.

[0x-auth]

@Whatsonyourmind Excellent analysis — all three points are on target.

On cosine degeneracy in low dimensions: Agreed that the GPU-only pod behavior is actually desirable. The cosine term naturally focuses on the dominant request dimension, which is what we want for a tiebreaker.

On phi as a weight: You're right — and we've already moved away from it. The original V1 (in this issue description) used φ-weighted alignment. The current V3 (in the design PR #1374) uses grid-search-derived weights (0.6 stddev balance / 0.2 alignment / 0.1 headroom) with no φ dependency. The "parameter-free" claim was from V1 and shouldn't carry forward. The V3 weights are empirically derived, not theoretically justified from φ.

On entropy: V3 replaced entropy with standard deviation, aligned with upstream K8s BalancedAllocation. The epsilon clamping issue doesn't apply to the current formulation, but good to keep in mind if entropy is revisited.

On DRF complementarity: Exactly right — DRF ensures cross-pod fairness, this scoring ensures per-node efficiency. They compose cleanly since they optimize different objectives.

The design PR (#1374) reflects all of these updates. Thanks for the thorough review.

[Whatsonyourmind]

@0x-auth Good to hear V3 already addressed the phi dependency and moved to empirically-derived weights. The stddev formulation is a reasonable substitute for entropy in this context — it penalizes imbalance without the edge-case handling entropy requires.

One note on the stddev vs entropy tradeoff for anyone following along: stddev penalizes large deviations quadratically (sensitive to outlier dimensions), while entropy penalizes uniformly across all dimensions. For GPU clusters where one dimension often dominates, stddev is actually the better choice — it more aggressively penalizes the "99% GPU / 2% CPU" fragmentation pattern.

Will watch #1374 for the landing.

[davidLif]

@0x-auth There is a dependency between "gpu", "gpu-compute", and "gpu-memory" resources. Without the user having a spesific way to request "gpu-compute" and "gpu-memory" separatly, I think that adding a more complicated function for bin-packing/spreading calculation might be premature.

Do you have any spesific scenario you currently expirence in your own cluster that drives this request? How does the pods look like?

[0x-auth]

@davidLif Good point — the GPU-compute vs GPU-memory separation is key context.

On the dependency: You're right that without separate gpu-compute and gpu-memory request fields, the multi-dimensional GPU scoring doesn't apply today. The proposal already scopes to CPU + Memory + GPU-Memory (per @enoodle's earlier note that GPU-compute isn't currently supported).

The scenario that drives this: The cross-dimensional imbalance I've seen is primarily between CPU and Memory (not GPU sub-dimensions). In mixed clusters with heterogeneous node types — some CPU-heavy (16 CPU / 32GB), some memory-heavy (8 CPU / 128GB) — the default scorers treat a node at 90% CPU / 10% RAM the same as one at 50% / 50%. The first has stranded RAM.

For a concrete example: an inference serving workload requesting 2 CPU + 16GB RAM + 1 GPU. LeastAllocated sends it to whichever node has the most total free resources. BalancedAllocation picks the node with lowest post-placement variance. But neither asks "does this pod's CPU/RAM ratio match what this node has available?" — that's the directional signal cosine alignment adds.

On prematurity: I agree that adding complexity for a problem that doesn't exist yet (gpu-compute vs gpu-memory) isn't useful. The 2D version (CPU + Memory balance with alignment tiebreaker) is where the measurable improvement comes from. The proposal generalizes to N dimensions but the immediate value is in 2-3D.

Would it be useful to narrow the design doc to CPU + Memory only and frame GPU-memory as a future extension?