<!--
**Note:** When your KEP is complete, all of these comment blocks should be removed.

Follow the guidelines of the [documentation style guide].
In particular, wrap lines to a reasonable length, to make it
easier for reviewers to cite specific portions, and to minimize diff churn on
updates.

[documentation style guide]: https://github.com/kubernetes/community/blob/master/contributors/guide/style-guide.md

To get started with this template:

- [ ] **Pick a hosting SIG.**
  Make sure that the problem space is something the SIG is interested in taking
  up. KEPs should not be checked in without a sponsoring SIG.
- [ ] **Create an issue in kubernetes/enhancements**
  When filing an enhancement tracking issue, please make sure to complete all
  fields in that template. One of the fields asks for a link to the KEP. You
  can leave that blank until this KEP is filed, and then go back to the
  enhancement and add the link.
- [ ] **Make a copy of this template directory.**
  Copy this template into the owning SIG's directory and name it
  `NNNN-short-descriptive-title`, where `NNNN` is the issue number (with no
  leading-zero padding) assigned to your enhancement above.
- [ ] **Fill out as much of the kep.yaml file as you can.**
  At minimum, you should fill in the "Title", "Authors", "Owning-sig",
  "Status", and date-related fields.
- [ ] **Fill out this file as best you can.**
  At minimum, you should fill in the "Summary" and "Motivation" sections.
  These should be easy if you've preflighted the idea of the KEP with the
  appropriate SIG(s).
- [ ] **Create a PR for this KEP.**
  Assign it to people in the SIG who are sponsoring this process.
- [ ] **Merge early and iterate.**
  Avoid getting hung up on specific details and instead aim to get the goals of
  the KEP clarified and merged quickly. The best way to do this is to just
  start with the high-level sections and fill out details incrementally in
  subsequent PRs.

Just because a KEP is merged does not mean it is complete or approved. Any KEP
marked as `provisional` is a working document and subject to change. You can
denote sections that are under active debate as follows:

```
<<[UNRESOLVED optional short context or usernames ]>>
Stuff that is being argued.
<<[/UNRESOLVED]>>
```

When editing KEPS, aim for tightly-scoped, single-topic PRs to keep discussions
focused. If you disagree with what is already in a document, open a new PR
with suggested changes.

One KEP corresponds to one "feature" or "enhancement" for its whole lifecycle.
You do not need a new KEP to move from beta to GA, for example. If
new details emerge that belong in the KEP, edit the KEP. Once a feature has become
"implemented", major changes should get new KEPs.

The canonical place for the latest set of instructions (and the likely source
of this file) is [here](/keps/NNNN-kep-template/README.md).

**Note:** Any PRs to move a KEP to `implementable`, or significant changes once
it is marked `implementable`, must be approved by each of the KEP approvers.
If none of those approvers are still appropriate, then changes to that list
should be approved by the remaining approvers and/or the owning SIG (or
SIG Architecture for cross-cutting KEPs).
-->
# KEP-5598: Opportunistic batching
<!--
This is the title of your KEP. Keep it short, simple, and descriptive. A good
title can help communicate what the KEP is and should be considered as part of
any review.
-->

<!--
A table of contents is helpful for quickly jumping to sections of a KEP and for
highlighting any additional information provided beyond the standard KEP
template.

Ensure the TOC is wrapped with
  <code>&lt;!-- toc --&rt;&lt;!-- /toc --&rt;</code>
tags, and then generate with `hack/update-toc.sh`.
-->

<!-- toc -->
- [Release Signoff Checklist](#release-signoff-checklist)
- [Summary](#summary)
- [Motivation](#motivation)
  - [Goals](#goals)
  - [Non-Goals](#non-goals)
- [Proposal](#proposal)
  - [Pod scheduling signature](#pod-scheduling-signature)
  - [Batching mechanism](#batching-mechanism)
    - [GetNodeHint](#getnodehint)
    - [StoreScheduleResults](#storescheduleresults)
    - [Integration with Scheduling Cycle](#integration-with-scheduling-cycle)
  - [Rescoring](#rescoring)
    - [Rescoring the Last Chosen Node](#rescoring-the-last-chosen-node)
    - [NormalizeScore on a Subset](#normalizescore-on-a-subset)
  - [Notes/Constraints/Caveats (Optional)](#notesconstraintscaveats-optional)
  - [Risks and Mitigations](#risks-and-mitigations)
    - [Plugins need to keep signatures up to date](#plugins-need-to-keep-signatures-up-to-date)
    - [Limited workload coverage](#limited-workload-coverage)
    - [No prior production history](#no-prior-production-history)
    - [Cached nodes are not re-filtered each cycle](#cached-nodes-are-not-re-filtered-each-cycle)
    - [Rescore mixes scores from different cluster states](#rescore-mixes-scores-from-different-cluster-states)
    - [Memory overhead from raw score caching](#memory-overhead-from-raw-score-caching)
- [Design Details](#design-details)
  - [Pod signature](#pod-signature)
  - [Test Plan](#test-plan)
      - [Prerequisite testing updates](#prerequisite-testing-updates)
      - [Unit tests](#unit-tests)
      - [Integration tests](#integration-tests)
      - [e2e tests](#e2e-tests)
  - [Graduation Criteria](#graduation-criteria)
    - [Beta](#beta)
    - [GA](#ga)
  - [Upgrade / Downgrade Strategy](#upgrade--downgrade-strategy)
  - [Version Skew Strategy](#version-skew-strategy)
- [Production Readiness Review Questionnaire](#production-readiness-review-questionnaire)
  - [Feature Enablement and Rollback](#feature-enablement-and-rollback)
  - [Rollout, Upgrade and Rollback Planning](#rollout-upgrade-and-rollback-planning)
  - [Monitoring Requirements](#monitoring-requirements)
  - [Dependencies](#dependencies)
  - [Scalability](#scalability)
  - [Troubleshooting](#troubleshooting)
- [Implementation History](#implementation-history)
- [Drawbacks](#drawbacks)
- [Alternatives](#alternatives)
  - [Comparison with Equivalence Cache (circa 2018)](#comparison-with-equivalence-cache-circa-2018)
  - [New Rescore Extension Point](#new-rescore-extension-point)
- [Future work](#future-work)
- [Infrastructure Needed (Optional)](#infrastructure-needed-optional)
<!-- /toc -->

## Release Signoff Checklist

<!--
**ACTION REQUIRED:** In order to merge code into a release, there must be an
issue in [kubernetes/enhancements] referencing this KEP and targeting a release
milestone **before the [Enhancement Freeze](https://git.k8s.io/sig-release/releases)
of the targeted release**.

For enhancements that make changes to code or processes/procedures in core
Kubernetes—i.e., [kubernetes/kubernetes], we require the following Release
Signoff checklist to be completed.

Check these off as they are completed for the Release Team to track. These
checklist items _must_ be updated for the enhancement to be released.
-->

Items marked with (R) are required *prior to targeting to a milestone / release*.

- [X] (R) Enhancement issue in release milestone, which links to KEP dir in [kubernetes/enhancements] (not the initial KEP PR)
- [X] (R) KEP approvers have approved the KEP status as `implementable`
- [X] (R) Design details are appropriately documented
- [X] (R) Test plan is in place, giving consideration to SIG Architecture and SIG Testing input (including test refactors)
  - [X] e2e Tests for all Beta API Operations (endpoints)
  - [X] (R) Ensure GA e2e tests meet requirements for [Conformance Tests](https://github.com/kubernetes/community/blob/master/contributors/devel/sig-architecture/conformance-tests.md)
  - [X] (R) Minimum Two Week Window for GA e2e tests to prove flake free
- [X] (R) Graduation criteria is in place
  - [X] (R) [all GA Endpoints](https://github.com/kubernetes/community/pull/1806) must be hit by [Conformance Tests](https://github.com/kubernetes/community/blob/master/contributors/devel/sig-architecture/conformance-tests.md) within one minor version of promotion to GA
- [X] (R) Production readiness review completed
- [X] (R) Production readiness review approved
- [X] "Implementation History" section is up-to-date for milestone
- [ ] User-facing documentation has been created in [kubernetes/website], for publication to [kubernetes.io]
- [ ] Supporting documentation—e.g., additional design documents, links to mailing list discussions/SIG meetings, relevant PRs/issues, release notes

<!--
**Note:** This checklist is iterative and should be reviewed and updated every time this enhancement is being considered for a milestone.
-->

[kubernetes.io]: https://kubernetes.io/
[kubernetes/enhancements]: https://git.k8s.io/enhancements
[kubernetes/kubernetes]: https://git.k8s.io/kubernetes
[kubernetes/website]: https://git.k8s.io/website

## Summary

This KEP proposes an opportunistic batching mechanism in the scheduler to improve performance of
scheduling many compatible pods at once, and to begin building the infrastructure required for gang
scheduling. To implement this mechanism we propose the following additions:

 - **Pod scheduling signature:** A signature that captures the properties of a pod that impact
   scoring and feasibility.
 - **Batching mechanism:** A mechanism to reuse the scheduling output from one pod to provide node
   hints for multiple subsequent pods with matching scheduling signatures.
 - **Opportunistic batching:** Transparent inclusion of the batching mechanism in the scheduler to
   improve the performance of targeted workloads that could benefit from it.
 - **Rescoring:** An extension to the batching mechanism that removes the one-pod-per-node
   limitation: when the last chosen node is still feasible, it is rescored in-place rather than
   flushing the batch.

## Motivation

Today our scheduling algorithm is O(num pods x num nodes). As the size of clusters and jobs continue
to increase, this leads to low performance when scheduling or rescheduling large jobs. This
increases user cost and slows down user jobs, both unpleasant impacts. Optimizations like this one
have the potential to dramatically reduce the cost of scheduling in these scenarios.

Gang scheduling and other multi-pod scheduling mechanisms require a way to consider multiple pods at
the same time. Opportunistic batching provides a starting point by introducing signatures and batch
state reuse, both foundational mechanisms, and including them in a transparent and incremental way.

A common pattern in batch and ML environments is to run a single user pod on each node alongside a
complement of daemonset pods. For these workloads, once a pod is placed on a node, that node is full
and can be skipped for subsequent pods. This allows the scheduler to reuse not only filtering but
also scoring results, reducing per-cycle cost.

However, not all workloads follow the one-pod-per-node pattern. For multi-pod-per-node pods (e.g., a
web server requesting 100m CPU / 128Mi memory) the previously chosen node remains feasible after
each placement, so naively checking for infeasibility would invalidate the cache on every cycle.
[kubernetes/kubernetes#137707] identifies three consequences if this case is unhandled:

1. **Redundant synchronous overhead.** The `RunFilterPlugins` call in `batchStateCompatible`
   executes on the critical scheduling path for every pod in a multi-pod-per-node batch without ever
   producing a useful result.
2. **Duplicate filtering.** The same node is filtered in `GetNodeHint` and then again in the
   filtering pass that immediately follows after batch state is invalidated.
3. **Cache invalidation every cycle.** The sorted node list is discarded on every cycle despite the
   pod signatures being identical, so the O(N) `Filter` and `Score` pipeline runs in full for every
   pod in the batch.

Rescoring solves this: when the last chosen node is still feasible, the scheduler rescores it
against the current pod and updates its rank in the cached list rather than discarding the batch
state. Both workload patterns, one-pod-per-node and multi-pod-per-node, are handled efficiently
within the same mechanism.

[kubernetes/kubernetes#137707]: https://github.com/kubernetes/kubernetes/issues/137707

### Goals

 * Improve the performance of scheduling large jobs on large clusters where the constraints are
   simple.
 * Begin building infrastructure to support gang scheduling and other "multi-pod" scheduling
   mechanisms.
 * Ensure that the infrastructure we build is maintainable as we update, add and remove plugins.
 * Reduce per-cycle scheduling cost for both one-pod-per-node and multi-pod-per-node workloads.
 * Provide a path where we can expand batching to apply to most or all workloads over the next few
   releases.
 * Allow users to continue to use out-of-tree plugins. For this KEP we need to ensure that out-of-
   tree plugins continue to work without requiring edits, although they may not be able to take
   advantage of the new feature without some edits.

### Non-Goals

 * Applying this optimization to all pods. Batching is transparent but limited to signable workloads
   in this KEP.
 * Adding gang scheduling. This is purely a performance improvement without dependency on the
   Workload API [KEP-4671](https://github.com/kubernetes/enhancements/pull/5558), although this work
   is intended to build toward it.
 * Supporting group-aware scoring plugins (`PodTopologySpread`, `InterPodAffinity`) for rescoring.
   These cause pods to be unsignable and are excluded from batching entirely.
 * Introducing a new `Rescore` plugin interface. That extension point is deferred to future work and
   described under [Alternatives](#alternatives).

## Proposal

The batching mechanism is applied transparently to simple cases in the scheduling cycle, reusing the
cached sorted node list from a previous cycle to provide node hints for subsequent identical pods.
More complex integrations are left to future work.

The proposal covers three components: pod scheduling signature, batching mechanism and rescoring.

### Pod scheduling signature

The pod scheduling signature identifies pods that are equivalent from a scheduling perspective: any
two pods with the same signature will receive identical scores and feasibility results for any given
set of nodes. Assigning a pod to a node must not change the feasibility or scoring of other nodes.
This is the invariant that allows cached results to be reused.

Pods whose scheduling depends on cross-pod state or global placement data, rather than only pod and
node attributes, receive a nil signature and fall back to the standard full-pipeline path.

A new framework interface allows out-of-tree plugins to construct a signature. Each plugin returns a
set of signature fragments that capture the pod attributes relevant to that plugin's scheduling
decisions. To construct a full signature, the framework collects fragments from all plugins and
marshals them into a single `PodSignature` (a byte slice). If any plugin cannot generate a signature
for a given pod, it returns an error status and a nil signature is produced for that pod, skipping
batching.

If any enabled plugin that participates in the PreScore, Score, PreFilter or Filter extension
points does not implement this interface, batching is disabled for all pods.

The signature interface and types are defined as follows:

```go
// A portion of a pod signature. The sign fragments from all plugins are combined
//  to create a unified signature.
type SignFragment struct {
	// Key identifies this fragment. Fragments with the same key should contain
	// the same value for the same pod.
	Key string

	// Value must be JSON-marshallable.
	Value any
}

// The signature for a given pod after all fragments are consolidated.
type PodSignature []byte

// SignPlugin is an interface that should be implemented by plugins that either filter
// or score pods to enable batching and gang scheduling optimizations.
type SignPlugin interface {
	Plugin
	// SignPod returns SignFragments for this pod.
	//
	// Return values:
	//   - Success: plugin can sign the pod, returns signature fragments
	//   - Unschedulable: plugin cannot sign pod (pod not eligible for batching)
	//   - Error: unexpected failure (pod not eligible for batching, error logged)
	SignPod(ctx context.Context, pod *v1.Pod) ([]SignFragment, *Status)
}
```
### Batching mechanism

The second component of this KEP is a batching mechanism. The batching mechanism provides two main
operations that are invoked during the scheduling cycle:

 * **GetNodeHint:** Returns a node hint for a pod with a valid signature by validating that cached
   scheduling results can be reused.
 * **StoreScheduleResults:** Stores the sorted scheduling results from a "canonical" pod for
   potential reuse with subsequent matching pods.

#### GetNodeHint

The `GetNodeHint` operation is called during the filtering phase, after PreFilter but before
evaluating individual nodes, to determine if we can reuse cached scheduling results from a previous
pod. It takes a pod with a signature and attempts to provide a node hint that will allow the
scheduler to take a fast path.

Before returning a hint, the operation validates that the cached batch state is compatible with the
current pod by checking:

1. **Cycle continuity:** The current scheduling cycle must be exactly one greater than the last
   cycle (no other pods were scheduled).
2. **Signature match:** The pod's signature must exactly match the cached signature.
3. **Cache freshness:** The cached data must be sufficiently recent to avoid relying on stale
   scheduling decisions.
4. **Last chosen node feasibility check:** Filter plugins are run against the node chosen in the
   previous cycle. Two outcomes are possible:
   - **Infeasible:** The node cannot host another pod from the batch (one-pod-per-node case),                                                                                                                                           
     either it is at capacity or a per-node constraint (such as a host port conflict) prevents                                                                                                                                            
     placement. The node is discarded and batch proceeds without it.
   - **Still feasible:** The node can host another pod (multi-pod-per-node case). This node is
     rescored (see [Rescoring the Last Chosen Node](#rescoring-the-last-chosen-node)).

If all checks pass, the operation pops the next best node from the cached sorted list and returns it
as a hint (see [Integration with Scheduling Cycle](#integration-with-scheduling-cycle) below for how
the hint is used).

If any check fails, the batch state is invalidated with the reason recorded in metrics, no hint is
provided, and the scheduler falls back to full evaluation of all nodes.

#### StoreScheduleResults

The `StoreScheduleResults` operation is called after a pod has been scheduled (after filtering,
scoring, and node selection). It stores scheduling results for potential reuse with subsequent pods.

The operation first records information about the last scheduling cycle (cycle number and chosen
node) for use in the next cycle's validation.

Then it determines whether to store new batch state:

**If a hint was used** (hintedNode == chosenNode):
- The cached result was reused successfully.
- No new batch state is stored; the existing batch continues.
- Statistics are recorded (batchedPods counter incremented).

**If no hint was provided or the hint was not used:**
- If the pod has a valid signature and there are remaining nodes in the sorted list, new batch state
  is created containing:
  - The pod's signature
  - The sorted list of remaining feasible nodes
  - Creation timestamp (for the expiration check)
- If the pod has no signature or no remaining nodes, no batch state is stored.

The batch state is kept in memory only and is constrained to a short-lived validity window to
prevent stale data from affecting scheduling decisions.

#### Integration with Scheduling Cycle

The `GetNodeHint` operation returns a hint string (node name) that is plugged directly into the
scheduling cycle.

During the scheduling cycle, if a node was hinted by the batching mechanism, the scheduler evaluates
that specific node first before iterating over all nodes. This "try one node first" is the fast
path. If the hinted node passes all filters, it is immediately returned as the only feasible node,
bypassing evaluation of all other nodes and scoring entirely.

If the hinted node fails filtering, the scheduler falls back to the normal path of evaluating all
nodes. This ensures correctness while providing significant performance benefits when the hint is
valid. The batching mechanism can be used in multiple places, including future gang scheduling
implementations, without requiring changes to the Pod API.

### Rescoring

#### Rescoring the Last Chosen Node

When `RunFilterPlugins` finds the last chosen node (node A) still feasible, rescoring runs instead
of flushing the batch:

1. Node A is re-inserted into the cached sorted list. Since it is still feasible, it can host
   additional pods.
2. `RunPreScorePlugins` is called for all plugins against the current pod to populate `CycleState`
   with the state required by `Score`.
3. `Score` is called for each scoring plugin against node A. The resulting score accurately 
   reflects pod N's placement.
4. `NormalizeScore` is called for each plugin over all nodes in the cached list (the re-inserted
   node A plus the remaining nodes).
5. The cached list is re-sorted by aggregate normalized score.
6. The top-ranked node is popped and returned as the hint for the current pod.

This is correct under the assumption that scoring is node-local: placing pod N on node A does not
affect the scores of other nodes. This holds for all signable pods. Group-aware scoring plugins
(which would violate it) already make pods unsignable and are excluded from batching entirely.

**Cost comparison:**

| Scenario | Batching disabled | Batching enabled |
|---|---|---|
| One-pod-per-node | O(N) filter + O(N) Score + O(N) NormalizeScore | O(1) filter, 0 scoring |
| Multi-pod-per-node | O(N) filter + O(N) Score + O(N) NormalizeScore | O(1) filter + O(P) PreScore + O(1) Score + O(M) NormalizeScore + O(M log M) sort |

Where P is the number of plugins and M is the number of nodes in the cached list (M ≤ N). For
multi-pod-per-node workloads M stays close to N since nodes are re-inserted each cycle. Both the
O(N) Filter pass and the O(N) Score pass are eliminated: only a single `RunFilterPlugins` call,
a single `PreScore` pass over all plugins O(P), and a single `Score` call run per cycle.
`NormalizeScore` over M cached nodes is the only remaining node-proportional cost, and it is
lightweight relative to `Score`: it is arithmetic normalization rather than plugin logic.

#### NormalizeScore on a Subset

To support rescoring, `batchState` also caches the raw score for each node in the cached list. When
rescoring, only the rescored node's raw score is updated; the rest remain valid under the node-local
scoring assumption.

`NormalizeScore` is applied to the cached node subset rather than all feasible nodes. When the cache
is fresh, meaning the cached list contains exactly the nodes a fresh full pipeline would filter to,
rescoring node A and normalizing all cached nodes produces identical results to a full pipeline run.
The raw scores of all other nodes are unchanged (node-local scoring), node A's raw score is updated
by the explicit `Score` call, and `NormalizeScore` sees the same set with the same scores.

The only source of divergence is cache staleness: if cluster state has changed since the initial
full pipeline run, the cached raw scores for non-rescored nodes may be slightly out of date. This is
bounded by the 500ms `maxBatchAge` expiry (see [Risks and Mitigations](#risks-and-mitigations)).

### Notes/Constraints/Caveats (Optional)

### Risks and Mitigations

#### Plugins need to keep signatures up to date

The cache requires plugin maintainers to keep their portion of the signature up-to-date. By putting
the logic into the plugin interface itself and restricting it to portions of the pod spec, the
surface area for divergence is minimized, but subtle dependencies can still creep in over time.

If signature drift becomes a problem, the signature could be codified as a reduced "Scheduling"
object containing only the fields relevant to scheduling decisions. Plugins that opt in would
receive only this object, making it structurally impossible for the signature and plugin logic to
diverge. This approach is deferred because plugin changes are expected to be infrequent and the
additional interface complexity is not justified at this stage.

#### Limited workload coverage

By limiting the supported feature set, batching may not apply to all workloads. This is mitigated by
targeting simple patterns first and providing a clear expansion path via the signing
mechanism and future group-aware plugin support.

#### No prior production history

Batching is a new code path with no prior production history. The built-in metrics provide visibility 
into how often batching triggers, how often the cache is invalidated and why. Feature gate is enabled 
by default, operators can disable it if unexpected behavior is observed.

#### Cached nodes are not re-filtered each cycle

Only `lastChosenNode` is re-filtered against the fresh snapshot each cycle. Other nodes in the
cached list are not re-checked, so a node that has become infeasible since the initial full pass may
remain in the list and be selected as a hint.

This is bounded by the existing `maxBatchAge` expiry (500ms): a batch that has been running longer
than 500ms is flushed and a full pipeline reruns. In a typical scheduling burst, where pods are
processed every few milliseconds, the window for meaningful node state drift is very small.
Operators can disable `OpportunisticBatching` to restore full-pipeline behavior if degradation is
observed.

#### Rescore mixes scores from different cluster states

When rescoring runs, `PreScore` is re-run for the current pod and `Score` is called only for the
last chosen node. The remaining cached nodes retain raw scores computed when the batch was created,
so the resulting ranking combines scores from two different cluster states and may diverge slightly
from a fresh full pipeline run.

This is bounded by the same 500ms `maxBatchAge` expiry: a batch older than 500ms is flushed and a
full pipeline reruns.

#### Memory overhead from raw score caching

`batchState` stores raw per-plugin scores for every node in the cached list to support rescoring.
The overhead is:

  `O(|cached list| × |scoring plugins|) × sizeof(int64)`

For a cluster with 5000 nodes and 10 scoring plugins, this is on the order of a few hundred
kilobytes per active batch. The cached list also shrinks over the lifetime of a batch as nodes are
popped and not re-inserted (one-pod-per-node case). Each scheduler profile maintains its own
`batchState`, so the total overhead scales with the number of active profiles - typically one or two
in practice.

## Design Details

### Pod signature

A pod scheduling signature is a hash of the pod's scheduling requirements. It is used to identify
pods that can be scheduled together. To optimize the scheduling cycle, the signature is calculated
and cached when a pod first enters the scheduling queue. By pre-calculating the signature during the
queuing phase, the scheduler avoids extra work during the time-sensitive scheduling process,
allowing larger batches to be handled more smoothly.

The following section lists the pod attributes used as the signature for each plugin. Plugins that
depend on cross-pod state or global placement data return an unsignable status; all others return a
deterministic signature fragment covering the relevant fields.

Note that the signature does not need to be stable across versions, or even invocations of the
scheduler. It only needs to be comparable between pods on a given running scheduler instance.

 * **DynamicResources:** Pods with dynamic resource claims are marked unsignable. Most DRA claims
   are node-specific and could be made signable with additional work; this is deferred to a future
   iteration.
 * **ImageLocality:** We use the canonicalized image names from the Volumes as the signature.
 * **InterPodAffinity:** If either the PodAffinity or PodAntiAffinity fields are set, the pod is
   marked unsignable, otherwise the pod labels need to be included in the signature.
 * **NodeAffinity:** We use the NodeAffinity and NodeSelector fields, plus any defaults set in
   configuration as the signature.
 * **NodeName:** We use the NodeName field as the signature.
 * **NodePorts:** We use the results from util.GetHostPorts(pod) as the signature.
 * **NodeResourcesBalancedAllocation:** We use the output of calculatePodResourceRequestList as the
   signature.
 * **NodeResourcesFit:** We use the output of the computePodResourceRequest function as the
   signature.
 * **NodeUnschedulable:** We use the Tolerations field as the signature.
 * **NodeVolumeLimits:** We use all Volume information except from Volumes of type ConfigMap or
   Secret.
 * **PodTopologySpread:** If the PodTopologySpread field is set, or it is not set but a default set
   of rules are applied, we mark the pod unsignable, otherwise it returns an empty signature.
   Because the plugin itself is creating the signature, it knows whether and what default rules
   apply.
 * **TaintToleration:** We use the Tolerations field as the signature.
 * **VolumeBinding:** Same as NodeVolumeLimits.
 * **VolumeRestrictions:** Same as NodeVolumeLimits.
 * **VolumeZone:** Same as NodeVolumeLimits.

### Test Plan

<!--
**Note:** *Not required until targeted at a release.*
The goal is to ensure that we don't accept enhancements with inadequate testing.

All code is expected to have adequate tests (eventually with coverage
expectations). Please adhere to the [Kubernetes testing guidelines][testing-guidelines]
when drafting this test plan.

[testing-guidelines]: https://git.k8s.io/community/contributors/devel/sig-testing/testing.md
-->

[X] I/we understand the owners of the involved components may require updates to existing tests to
make this code solid enough prior to committing the changes necessary to implement this enhancement.

##### Prerequisite testing updates

<!--
Based on reviewers feedback describe what additional tests need to be added prior
implementing this enhancement to ensure the enhancements have also solid foundations.
-->

##### Unit tests

<!--
In principle every added code should have complete unit test coverage, so providing
the exact set of tests will not bring additional value.
However, if complete unit test coverage is not possible, explain the reason of it
together with explanation why this is acceptable.
-->

<!--
Additionally, for Alpha try to enumerate the core package you will be touching
to implement this enhancement and provide the current unit coverage for those
in the form of:
- <package>: <date> - <current test coverage>
The data can be easily read from:
https://testgrid.k8s.io/sig-testing-canaries#ci-kubernetes-coverage-unit

This can inform certain test coverage improvements that we want to do before
extending the production code to implement this enhancement.
-->

###### Coverage of existing packages

Will add an extra function and test for plugins we touch.

- `k8s.io/kubernetes/pkg/scheduler`: `2025-10-7` - `86.1`
- `k8s.io/kubernetes/pkg/scheduler/framework`: `2025-10-7` - `51.8`
- `k8s.io/kubernetes/pkg/scheduler/framework/runtime`: `2025-10-7` - `84.3`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/dynamicresources`: `2025-10-7` - `80.5`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/imagelocality`: `2025-10-7` - `86.2`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/interpodaffinity`: `2025-10-7` - `89.7`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/nodeaffinity`: `2025-10-7` - `85.8`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/nodename`: `2025-10-7` - `50`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/nodeports`: `2025-10-7` - `83.7`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/noderesources`: `2025-10-7` - `89.5`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/nodeunschedulable`: `2025-10-7` - `87.1`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/nodevolumelimits`: `2025-10-7` - `73.7`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/podtopologyspread`: `2025-10-7` - `87.8`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/tainttoleration`: `2025-10-7` - `86.9`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/volumebinding`: `2025-10-7` - `83.9`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/volumerestrictions`: `2025-10-7` - `74`
- `k8s.io/kubernetes/pkg/scheduler/framework/plugins/volumezone`: `2025-10-7` - `84.8`

###### New unit tests

- `schedule_one_test.go` - Add test cases for opportunistic batching.
- `signature_test.go` - Test cases for the framework signature call and the helper class.
- `signature_consistency_test.go` - Test cases to ensure the signature captures all the necessary
  information. A range of pod specs and node definitions are run through the filtering/scoring code;
  pods with matching signatures must always receive equivalent results.
- `batching_test.go` - Test cases for the batching mechanism, separate from the actual integration
  into the scheduling pipeline.

Rescoring-specific unit tests (will be added to `batching_test.go` and `schedule_one_test.go`):
- `RunPreScorePlugins` is called for all plugins before `Score` during rescoring.
- Raw score updated only for the rescored node; other nodes' cached scores unchanged.
- `NormalizeScore` called once per plugin with the full cached node list (including re-inserted
  `lastChosenNode`).
- Returned hint is the node with the highest aggregate normalized score.
- Sorted list after the hint pop contains the correct remaining nodes.
- Raw scores are correctly populated by `StoreScheduleResults` after a full pipeline run.

##### Integration tests

<!--
Integration tests are contained in https://git.k8s.io/kubernetes/test/integration.
Integration tests allow control of the configuration parameters used to start the binaries under test.
This is different from e2e tests which do not allow configuration of parameters.
Doing this allows testing non-default options and multiple different and potentially conflicting command line options.
For more details, see https://github.com/kubernetes/community/blob/master/contributors/devel/sig-testing/testing-strategy.md

If integration tests are not necessary or useful, explain why.
-->

Integration tests:
- `scheduler_perf` tests measuring scheduling throughput with batching enabled and disabled for
  representative scenarios.
- End-to-end consistency: Tests running pods through the scheduler end-to-end with batching enabled
  and disabled, verifying that scheduling decisions are the same.
- Add a correctness test: schedule identical pods in a multi-pod-per-node workload with batching
  enabled and disabled. Verify that all placements are feasible (all filter plugins pass for the
  chosen node) and no scheduling constraints are violated.
- Add a multi-pod-per-node scenario to scheduler_perf and measure throughput with batching enabled
  and disabled; batching enabled should show measurably higher throughput.
- Record scheduler memory usage in the multi-pod-per-node `scheduler_perf` run to validate the
  cached raw score overhead stays within expected bounds.

<!--
This question should be filled when targeting a release.
For Alpha, describe what tests will be added to ensure proper quality of the enhancement.

For Beta and GA, document that tests have been written,
have been executed regularly, and have been stable.
This can be done with:
- permalinks to the GitHub source code
- links to the periodic job (typically https://testgrid.k8s.io/sig-release-master-blocking#integration-master), filtered by the test name
- a search in the Kubernetes bug triage tool (https://storage.googleapis.com/k8s-triage/index.html)
-->

<!-- [test name](https://github.com/kubernetes/kubernetes/blob/2334b8469e1983c525c0c6382125710093a25883/test/integration/...): [integration master](https://testgrid.k8s.io/sig-release-master-blocking#integration-master?include-filter-by-regex=MyCoolFeature), [triage search](https://storage.googleapis.com/k8s-triage/index.html?test=MyCoolFeature)
-->

##### e2e tests

<!--
This question should be filled when targeting a release.
For Alpha, describe what tests will be added to ensure proper quality of the enhancement.

For Beta and GA, document that tests have been written,
have been executed regularly, and have been stable.
This can be done with:
- permalinks to the GitHub source code
- links to the periodic job (typically a job owned by the SIG responsible for the feature), filtered by the test name
- a search in the Kubernetes bug triage tool (https://storage.googleapis.com/k8s-triage/index.html)

We expect no non-infra related flakes in the last month as a GA graduation criteria.
If e2e tests are not necessary or useful, explain why.
-->

- Run the existing scheduling e2e tests with batching enabled and disabled, to ensure they pass in
  both cases.

<!--
- [test name](https://github.com/kubernetes/kubernetes/blob/2334b8469e1983c525c0c6382125710093a25883/test/e2e/...): [SIG ...](https://testgrid.k8s.io/sig-...?include-filter-by-regex=MyCoolFeature), [triage search](https://storage.googleapis.com/k8s-triage/index.html?test=MyCoolFeature)
-->

### Graduation Criteria

<!--
**Note:** *Not required until targeted at a release.*

Define graduation milestones.

These may be defined in terms of API maturity, [feature gate] graduations, or as
something else. The KEP should keep this high-level with a focus on what
signals will be looked at to determine graduation.

Consider the following in developing the graduation criteria for this enhancement:
- [Maturity levels (`alpha`, `beta`, `stable`)][maturity-levels]
- [Feature gate][feature gate] lifecycle
- [Deprecation policy][deprecation-policy]

Clearly define what graduation means by either linking to the [API doc
definition](https://kubernetes.io/docs/concepts/overview/kubernetes-api/#api-versioning)
or by redefining what graduation means.

In general we try to use the same stages (alpha, beta, GA), regardless of how the
functionality is accessed.

[feature gate]: https://git.k8s.io/community/contributors/devel/sig-architecture/feature-gates.md
[maturity-levels]: https://git.k8s.io/community/contributors/devel/sig-architecture/api_changes.md#alpha-beta-and-stable-versions
[deprecation-policy]: https://kubernetes.io/docs/reference/using-api/deprecation-policy/

Below are some examples to consider, in addition to the aforementioned [maturity levels][maturity-levels].

#### Alpha

- Feature implemented behind a feature flag
- Initial e2e tests completed and enabled

#### Beta

- Gather feedback from developers and surveys
- Complete features A, B, C
- Additional tests are in Testgrid and linked in KEP
- More rigorous forms of testing—e.g., downgrade tests and scalability tests
- All functionality completed
- All security enforcement completed
- All monitoring requirements completed
- All testing requirements completed
- All known pre-release issues and gaps resolved

**Note:** Beta criteria must include all functional, security, monitoring, and testing requirements along with resolving all issues and gaps identified

#### GA

- N examples of real-world usage
- N installs
- Allowing time for feedback
- All issues and gaps identified as feedback during beta are resolved

**Note:** GA criteria must not include any functional, security, monitoring, or testing requirements.  Those must be beta requirements.

**Note:** Generally we also wait at least two releases between beta and
GA/stable, because there's no opportunity for user feedback, or even bug reports,
in back-to-back releases.

**For non-optional features moving to GA, the graduation criteria must include
[conformance tests].**

[conformance tests]: https://git.k8s.io/community/contributors/devel/sig-architecture/conformance-tests.md

#### Deprecation

- Announce deprecation and support policy of the existing flag
- Two versions passed since introducing the functionality that deprecates the flag (to address version skew)
- Address feedback on usage/changed behavior, provided on GitHub issues
- Deprecate the flag
-->

#### Beta

- Feature implemented behind a feature flag
- Initial signature implementations for all in-tree plugins (note that some, as described in the
  section, will always return unsignable if the pod is configured to use them).
- Monitoring
- Hand-done perf test runs
- Integration tests
- Initial e2e tests completed and enabled
- Handle common one-pod-per-node batches: host ports and resources
- Parameter tuning (batch sizes, etc.)
- Pod scheduling signature is cached and reused across scheduling attempts, eliminating per-cycle
  recomputation.
- Unit tests for rescoring: score caching and update, cached nodes order after rescore.
- Integration perf tests demonstrating improvement for the multi-pod-per-node scenario.
- `scheduler_batch_rescore_attempts_total` and `scheduler_batch_rescore_duration_seconds` metrics
  exported.

#### GA

- At least one production deployment with evidence of improved scheduling throughput.

### Upgrade / Downgrade Strategy

<!--
If applicable, how will the component be upgraded and downgraded? Make sure
this is in the test plan.

Consider the following in developing an upgrade/downgrade strategy for this
enhancement:
- What changes (in invocations, configurations, API use, etc.) is an existing
  cluster required to make on upgrade, in order to maintain previous behavior?
- What changes (in invocations, configurations, API use, etc.) is an existing
  cluster required to make on upgrade, in order to make use of the enhancement?
-->

Users should continue to see the same behavior, just with better performance. 
All batching state is in-memory only.

### Version Skew Strategy

<!--
If applicable, how will the component handle version skew with other
components? What are the guarantees? Make sure this is in the test plan.

Consider the following in developing a version skew strategy for this
enhancement:
- Does this enhancement involve coordinating behavior in the control plane and nodes?
- How does an n-3 kubelet or kube-proxy without this feature available behave when this feature is used?
- How does an n-1 kube-controller-manager or kube-scheduler without this feature available behave when this feature is used?
- Will any other components on the node change? For example, changes to CSI,
  CRI or CNI may require updating that component before the kubelet.
-->

This feature should be localized to the scheduler. So long as the scheduler is correctly built, we
should not require other interactions from components in the system. Scheduler plugins will need to
implement new methods to take advantage of the feature, but if they do nothing the feature will
simply end up disabled.

## Production Readiness Review Questionnaire

<!--

Production readiness reviews are intended to ensure that features merging into
Kubernetes are observable, scalable and supportable; can be safely operated in
production environments, and can be disabled or rolled back in the event they
cause increased failures in production. See more in the PRR KEP at
https://git.k8s.io/enhancements/keps/sig-architecture/1194-prod-readiness.

The production readiness review questionnaire must be completed and approved
for the KEP to move to `implementable` status and be included in the release.

In some cases, the questions below should also have answers in `kep.yaml`. This
is to enable automation to verify the presence of the review, and to reduce review
burden and latency.

The KEP must have a approver from the
[`prod-readiness-approvers`](http://git.k8s.io/enhancements/OWNERS_ALIASES)
team. Please reach out on the
[#prod-readiness](https://kubernetes.slack.com/archives/CPNHUMN74) channel if
you need any help or guidance.
-->

### Feature Enablement and Rollback

<!--
This section must be completed when targeting alpha to a release.
-->

###### How can this feature be enabled / disabled in a live cluster?

<!--
Pick one of these and delete the rest.

Documentation is available on [feature gate lifecycle] and expectations, as
well as the [existing list] of feature gates.

[feature gate lifecycle]: https://git.k8s.io/community/contributors/devel/sig-architecture/feature-gates.md
[existing list]: https://kubernetes.io/docs/reference/command-line-tools-reference/feature-gates/
-->

- [X] Feature gate (also fill in values in `kep.yaml`)
  - Feature gate name: `OpportunisticBatching`
  - Components depending on the feature gate: `kube-scheduler`

###### Does enabling the feature change any default behavior?

<!--
Any change of default behavior may be surprising to users or break existing
automations, so be extremely careful here.
-->

No, it should not. Batching will improve the performance of some workloads, but should be
transparent otherwise.

###### Can the feature be disabled once it has been enabled (i.e. can we roll back the enablement)?

<!--
Describe the consequences on existing workloads (e.g., if this is a runtime
feature, can it break the existing applications?).

Feature gates are typically disabled by setting the flag to `false` and
restarting the component. No other changes should be necessary to disable the
feature.

NOTE: Also set `disable-supported` to `true` or `false` in `kep.yaml`.
-->

Yes, it can be disabled. Because it only keeps in-memory state, setting the flag to false and
restarting the scheduler should clear any previous state.

###### What happens if we reenable the feature if it was previously rolled back?

This feature only maintains in-memory, in-flight state, so changing the feature gate, which restarts
the scheduler, should not cause issues with a running system.

###### Are there any tests for feature enablement/disablement?

<!--
The e2e framework does not currently support enabling or disabling feature
gates. However, unit tests in each component dealing with managing data, created
with and without the feature, are necessary. At the very least, think about
conversion tests if API types are being modified.

Additionally, for features that are introducing a new API field, unit tests that
are exercising the `switch` of feature gate itself (what happens if I disable a
feature gate after having objects written with the new field) are also critical.
You can take a look at one potential example of such test in:
https://github.com/kubernetes/kubernetes/pull/97058/files#diff-7826f7adbc1996a05ab52e3f5f02429e94b68ce6bce0dc534d1be636154fded3R246-R282
-->

Not needed, as described above.

### Rollout, Upgrade and Rollback Planning

<!--
This section must be completed when targeting beta to a release.
-->

###### How can a rollout or rollback fail? Can it impact already running workloads?

<!--
Try to be as paranoid as possible - e.g., what if some components will restart
mid-rollout?

Be sure to consider highly-available clusters, where, for example,
feature flags will be enabled on some API servers and not others during the
rollout. Similarly, consider large clusters and how enablement/disablement
will rollout across nodes.
-->

Rollout can fail if the feature is faulty, causing pods to either not schedule or schedule
incorrectly. Already-running pods are not affected; the feature only influences placement decisions
for pending pods.

###### What specific metrics should inform a rollback?

<!--
What signals should users be paying attention to when the feature is young
that might indicate a serious problem?
-->

- `scheduler_pod_scheduling_sli_duration_seconds` - rising p99 indicates a scheduling regression.
- `scheduler_schedule_attempts_total` (unschedulable or error) - unexpected increase.
- `scheduler_batch_attempts_total` - confirms batching is being triggered; drop suggests pods are no
  longer signable.
- `scheduler_batch_cache_flushed_total` - unexpected spikes indicate the cache is being invalidated
  more than expected.
- `scheduler_batch_rescore_attempts_total` - zero value for a multi-pod-per-node workload 
  means those pods are not being rescored and the full pipeline runs for every cycle.
- `scheduler_batch_rescore_duration_seconds` - unexpected latency in the rescore path.
- `process_resident_memory_bytes` - unexpected growth may indicate cached raw scores
  accumulating beyond expected bounds.

###### Were upgrade and rollback tested? Was the upgrade->downgrade->upgrade path tested?

<!--
Describe manual testing that was done and the outcomes.
Longer term, we may want to require automated upgrade/rollback tests, but we
are missing a bunch of machinery and tooling and can't do that now.
-->

Upgrade and downgrade should be simple due the feature being in-memory. But we will test the path
before GA.

###### Is the rollout accompanied by any deprecations and/or removals of features, APIs, fields of API types, flags, etc.?

<!--
Even if applying deprecation policies, they may still surprise some users.
-->

No.

### Monitoring Requirements

<!--
This section must be completed when targeting beta to a release.

For GA, this section is required: approvers should be able to confirm the
previous answers based on experience in the field.
-->

###### How can an operator determine if the feature is in use by workloads?

<!--
Ideally, this should be a metric. Operations against the Kubernetes API (e.g.,
checking if there are objects with field X set) may be a last resort. Avoid
logs or events for this purpose.
-->

Query `scheduler_batch_attempts_total` - a non-zero value confirms that batching is active for at
least some pods. Query `scheduler_batch_rescore_attempts_total` - a non-zero value confirms that
rescoring is triggering for multi-pod-per-node workloads.

###### How can someone using this feature know that it is working for their instance?

<!--
For instance, if this is a pod-related feature, it should be possible to determine if the feature is functioning properly
for each individual pod.
Pick one more of these and delete the rest.
Please describe all items visible to end users below with sufficient detail so that they can verify correct enablement
and operation of this feature.
Recall that end users cannot usually observe component logs or access metrics.
-->

Operators can observe `scheduler_batch_attempts_total` and `scheduler_batch_rescore_attempts_total`
increasing as batches are processed, and `scheduler_pod_scheduling_sli_duration_seconds` improving
for batch workloads. End users cannot directly observe the feature; its effect is transparent, their
pods are scheduled faster.

###### What are the reasonable SLOs (Service Level Objectives) for the enhancement?

<!--
This is your opportunity to define what "normal" quality of service looks like
for a feature.

It's impossible to provide comprehensive guidance, but at the very
high level (needs more precise definitions) those may be things like:
  - per-day percentage of API calls finishing with 5XX errors <= 1%
  - 99% percentile over day of absolute value from (job creation time minus expected
    job creation time) for cron job <= 10%
  - 99.9% of /health requests per day finish with 200 code

These goals will help you determine what you need to measure (SLIs) in the next
question.
-->

The existing scheduler SLOs apply. The feature should not increase scheduling latency for signable
workloads; it should decrease it.

###### What are the SLIs (Service Level Indicators) an operator can use to determine the health of the service?

<!--
Pick one more of these and delete the rest.
-->

- [X] Metrics
  - `scheduler_pod_scheduling_sli_duration_seconds` - overall scheduling latency
  - `scheduler_batch_attempts_total` - counts of batching attempt results
  - `scheduler_batch_cache_flushed_total` - cache invalidation rate and reasons
  - `scheduler_get_node_hint_duration_seconds` - hint path latency
  - `scheduler_store_schedule_results_duration_seconds` - result storage latency
  - `scheduler_batch_rescore_attempts_total` - counts of rescoring attempt results
  - `scheduler_batch_rescore_duration_seconds` - per-cycle cost of the rescore path

###### Are there any missing metrics that would be useful to have to improve observability of this feature?

<!--
Describe the metrics themselves and the reasons why they weren't added (e.g., cost,
implementation difficulties, etc.).
-->

We will add new metrics to identify behavior. This includes:
- Batched vs non-batched pods - Identify how often a pod can be batched vs not.
- Counts of non-batching reasons - This can include plugin signatures, feasibility checks, etc.

### Dependencies

<!--
This section must be completed when targeting beta to a release.
-->

###### Does this feature depend on any specific services running in the cluster?

<!--
Think about both cluster-level services (e.g. metrics-server) as well
as node-level agents (e.g. specific version of CRI). Focus on external or
optional services that are needed. For example, if this feature depends on
a cloud provider API, or upon an external software-defined storage or network
control plane.

For each of these, fill in the following—thinking about running existing user workloads
and creating new ones, as well as about cluster-level services (e.g. DNS):
  - [Dependency name]
    - Usage description:
      - Impact of its outage on the feature:
      - Impact of its degraded performance or high-error rates on the feature:
-->

No.

### Scalability

<!--
For alpha, this section is encouraged: reviewers should consider these questions
and attempt to answer them.

For beta, this section is required: reviewers must answer these questions.

For GA, this section is required: approvers should be able to confirm the
previous answers based on experience in the field.
-->

###### Will enabling / using this feature result in any new API calls?

<!--
Describe them, providing:
  - API call type (e.g. PATCH pods)
  - estimated throughput
  - originating component(s) (e.g. Kubelet, Feature-X-controller)
Focusing mostly on:
  - components listing and/or watching resources they didn't before
  - API calls that may be triggered by changes of some Kubernetes resources
    (e.g. update of object X triggers new updates of object Y)
  - periodic API calls to reconcile state (e.g. periodic fetching state,
    heartbeats, leader election, etc.)
-->

No.

###### Will enabling / using this feature result in introducing new API types?

<!--
Describe them, providing:
  - API type
  - Supported number of objects per cluster
  - Supported number of objects per namespace (for namespace-scoped objects)
-->

No.

###### Will enabling / using this feature result in any new calls to the cloud provider?

<!--
Describe them, providing:
  - Which API(s):
  - Estimated increase:
-->

No.

###### Will enabling / using this feature result in increasing size or count of the existing API objects?

<!--
Describe them, providing:
  - API type(s):
  - Estimated increase in size: (e.g., new annotation of size 32B)
  - Estimated amount of new objects: (e.g., new Object X for every existing Pod)
-->

No.

###### Will enabling / using this feature result in increasing time taken by any operations covered by existing SLIs/SLOs?

<!--
Look at the [existing SLIs/SLOs].

Think about adding additional work or introducing new steps in between
(e.g. need to do X to start a container), etc. Please describe the details.

[existing SLIs/SLOs]: https://git.k8s.io/community/sig-scalability/slos/slos.md#kubernetes-slisslos
-->

No, it should result in decreased time for scheduling operations.

###### Will enabling / using this feature result in non-negligible increase of resource usage (CPU, RAM, disk, IO, ...) in any components?

<!--
Things to keep in mind include: additional in-memory state, additional
non-trivial computations, excessive access to disks (including increased log
volume), significant amount of data sent and/or received over network, etc.
This through this both in small and large cases, again with respect to the
[supported limits].

[supported limits]: https://git.k8s.io/community//sig-scalability/configs-and-limits/thresholds.md
-->

No, it should not.

###### Can enabling / using this feature result in resource exhaustion of some node resources (PIDs, sockets, inodes, etc.)?

<!--
Focus not just on happy cases, but primarily on more pathological cases
(e.g. probes taking a minute instead of milliseconds, failed pods consuming resources, etc.).
If any of the resources can be exhausted, how this is mitigated with the existing limits
(e.g. pods per node) or new limits added by this KEP?

Are there any tests that were run/should be run to understand performance characteristics better
and validate the declared limits?
-->

No, it should not.

### Troubleshooting

<!--
This section must be completed when targeting beta to a release.

For GA, this section is required: approvers should be able to confirm the
previous answers based on experience in the field.

The Troubleshooting section currently serves the `Playbook` role. We may consider
splitting it into a dedicated `Playbook` document (potentially with some monitoring
details). For now, we leave it here.
-->

###### How does this feature react if the API server and/or etcd is unavailable?

The same as the scheduler does today.

###### What are other known failure modes?

<!--
For each of them, fill in the following information by copying the below template:
  - [Failure mode brief description]
    - Detection: How can it be detected via metrics? Stated another way:
      how can an operator troubleshoot without logging into a master or worker node?
    - Mitigations: What can be done to stop the bleeding, especially for already
      running user workloads?
    - Diagnostics: What are the useful log messages and their required logging
      levels that could help debug the issue?
      Not required until feature graduated to beta.
    - Testing: Are there any tests for failure mode? If not, describe why.
-->

- [Increased pod scheduling latencies]
  - Detection: `scheduler_pod_scheduling_sli_duration_seconds` rises after enabling the feature.
  - Mitigations: disable `OpportunisticBatching` to restore full-pipeline behavior.
  - Diagnostics: check `scheduler_batch_rescore_duration_seconds` for rescore path overhead; check
    `scheduler_batch_cache_flushed_total` for unexpected invalidation spikes.
  - Testing: integration perf tests establish expected latency bounds.

- [Pods scheduled on incorrect nodes]
  - Detection: pods on nodes where they should not be (affinity violations, resource overcommit).
  - Mitigations: disable `OpportunisticBatching`.
  - Diagnostics: check batching metrics and scheduler logs.
  - Testing: correctness integration tests run scheduling with batching enabled and disabled and
    compare placements.

###### What steps should be taken if SLOs are not being met to determine the problem?

1. Check `scheduler_batch_attempts_total` - a drop or zero value indicates pods are not being
   batched. Verify signatures are being generated and the gate is enabled.
2. Check `scheduler_batch_cache_flushed_total` - high flush rates indicate the cache is being
   invalidated frequently. Examine the flush reason labels.
3. Check `scheduler_batch_rescore_attempts_total` - unexpectedly low for a multi-pod-per-node
   workload indicates rescoring is not triggering.
4. Check `scheduler_batch_rescore_duration_seconds` - identify if the rescore path is slow for
   specific plugins.

## Implementation History

<!--
Major milestones in the lifecycle of a KEP should be tracked in this section.
Major milestones might include:
- the `Summary` and `Motivation` sections being merged, signaling SIG acceptance
- the `Proposal` section being merged, signaling agreement on a proposed design
- the date implementation started
- the first Kubernetes release where an initial version of the KEP was available
- the version of Kubernetes where the KEP graduated to general availability
- when the KEP was retired or superseded
-->

- 2024-05-22: Initial KEP proposal introduced as [Enhancements PR #5599](https://github.com/kubernetes/enhancements/pull/5599).
- 2025-11-13: Initial version implemented [Kubernetes PR #135231](https://github.com/kubernetes/kubernetes/pull/135231).
- 2026-02-04: Optimized the implementation by caching the pod signature, thereby removing the computation from the critical scheduling path ([Kubernetes PR #136579](https://github.com/kubernetes/kubernetes/pull/136579)).
- 2026-04-26: Rescoring extension incorporated into this KEP to support multi-pod-per-node workloads.

## Drawbacks

<!--
Why should this KEP _not_ be implemented?
-->

## Alternatives

<!--
What other approaches did you consider, and why did you rule them out? These do
not need to be as detailed as the proposal, but should include enough
information to express the idea and why it was not acceptable.
-->

### Comparison with Equivalence Cache (circa 2018)

This KEP is addressing a very similar problem to the Equivalence Cache (eCache), an approach
suggested in 2018 and then retracted because it became extremely complex. While this KEP addresses a
similar problem it does so in a very different way, which we believe avoids the issues experienced
by the eCache

The issues experienced by eCache were:

 * eCache performance was still O(num nodes).
 * eCache was complex
 * eCache was tightly coupled with plugins.

 We'll address each in turn, but at a high level the differences stem from our scope reduction in
 this cache, where we focus on simple constraints in a one-pod-per-node world, and are comfortable
 extending our "race" period slightly.

 #### eCache performance was still O(num nodes)

 The eCache was caching a fundamentally different result than this cache. In the case of the eCache
 they were caching the results of a predicate p, (which is sounds like was one of a number of ops
 for a given plugin) for a specific pod and node. This meant the number of cache lookups per pod was
 O(num nodes * num predicates) where num predicates was O(num plugins). Because the cache was so
 fine-grained, the cache lookups were, in many cases, more expensive than the actual computation.
 This also meant that while the cache could improve performance, it fundamentally did not remove the
 O(num nodes) nature of the per pod computation.

 In the case of this cache, we are looking up the entire host filtering and scoring for a single
 pod, so the number of cache lookups per pod is 1. We are caching the entire filtering / scoring
 result, so the map lookup is guaranteed to be faster even than just iterating over the plugins
 themselves, let alone the computation needed to filter / score. As the number of nodes go up, the
 fact that the cache lookup is O(1) per pod will make it an increasingly perfromant alternative to
 the full computation.

 We can cache this more granular data because we only cache for simple plugins, and in fact avoid
 the complex plugins entirely. Thus we do not need to be concerned about cross pod dependencies,
 meaning we do not need to try to keep detailed information up-to-date. Because we assume one-pod-
 per-node and some amount of "staleness" we simply need to invalidate whole hosts, rather than
 requiring upkeep of complex predicate results required to keep the eCache functional.

 #### eCache was complex

 Because the eCache cached predicates, the logic for computing these results went into the cache as
 well. This meant that significant amount of the plugin functionality was replicated in the cache
 layer. This added significant complexity to the cache, and also made keeping the cache results
 themselves up to date complex, involving multiple pods, etc. Because the eCache only improved
 performance for complex queries, it needed to include this complexity to provide value.

 In contrast, the signature used in this cache is just a subset of the pod object, without complex
 logic. It is static and as the pod object changes slowly, it will change slowly as well. In
 addition, we explicitly avoid all the complex plugins in this cache because they are rarely used.
 Thus we do not have the same complexity needed in the cache.
 
 #### eCache was tightly coupled with plugins
 
 Because a significant amount of the plugin complexity made into the eCache, it was difficult for
 plugin owners to keep the things in sync. Since in this cache the signature is just parts of the
 pod object, and the pod object is fairly stable, this makes keeping the signature up to date a much
 simpler task. The creation of the signature is also spread across the plugins themselves, so
 instead of needing to keep the cache up to date, plugin owners simply have a new function they need
 to manage within their plugin, which the cache only aggregates.

 We will also provide tests that evaluate different pod configurations against different node
 configurations and ensure that any time the signatures match the results do as well. This will help
 us catch issues in the future, in addition to providing testing opportunities in other areas.

See https://github.com/kubernetes/kubernetes/pull/65714#issuecomment-410016382 as starting point on
eCache.
 
### New Rescore Extension Point

A new `Rescore` plugin interface could be introduced, allowing plugins to declare which nodes are
affected by the most recent placement and provide fresh raw scores for them. The framework then
combines those with the cached raw scores for unaffected nodes and calls `NormalizeScore` on the
full cached set — the same normalization flow as in the main pipeline.

```go
// RescorePlugin is an optional interface plugins may implement to support
// incremental rescoring during opportunistic batching.
type RescorePlugin interface {
    Plugin
    // Rescore is called after pod N is placed on placedNode. It returns raw
    // (pre-NormalizeScore) scores for every node whose score is affected by
    // the placement. The framework combines these with cached raw scores for
    // unaffected nodes and runs NormalizeScore over the full cached set.
    // Plugins with node-local scoring return scores for placedNode only.
    // Group-aware plugins may return scores for multiple nodes.
    //
    // Return values:
    //   - Success: map of affected node raw scores (may be empty if no scores changed)
    //   - Error: unexpected failure; batch state is invalidated
    Rescore(ctx context.Context, state *CycleState, pod *v1.Pod, placedNode NodeInfo, cachedNodes []NodeInfo) (map[string]int64, *Status)
}
```

This KEP's rescoring approach is the implicit special case of this design: it always assumes only
`placedNode` is affected (node-local scoring), runs `PreScore` and then calls `Score` to get its
raw score, and normalizes the full cached set. The `Rescore` extension point generalizes that by 
letting group-aware plugins declare additional affected nodes and provide their raw scores.

Pros:
- Semantically correct: plugins can provide correct raw scores for any affected nodes, including
  related-node effects from group-aware plugins.
- Opens the path to eventually supporting batching for pods with `PodTopologySpread` or
  `InterPodAffinity` constraints.

Cons:
- Requires every in-tree scoring plugin to be updated to implement `Rescore`.
- The related-node capability it enables is not usable until the signature mechanism is also
  extended, which is a separate, larger change.
- Adds permanent plugin API surface that must be maintained even when its primary benefit (group-
  aware rescoring) is not yet available.
- All currently signable pods use node-local scoring plugins, for which this KEP's rescoring
  approach is already correct.

This KEP's approach can be cleanly replaced by a dedicated `Rescore` extension point in a future.

## Future work

- **Group-aware plugin signability**: Pods that use `PodTopologySpread`, `InterPodAffinity`, or
  other group-aware scoring plugins are currently unsignable and receive no batching benefit.
  Extending the signature mechanism to handle these plugins, possibly by incorporating their
  constraints into the signature itself, would unlock batching for additional workloads.
- **PreScore optimization**: The current rescoring flow runs `RunPreScorePlugins` on every rescore
  cycle to populate `CycleState` before calling `Score`. This is not optimal. A more efficient
  approach would introduce a `PreScoreExtension` interface, analogous to the existing
  `PreFilterExtension`, with an `AddPod` method that plugins implement to incrementally update
  `CycleState` when a pod is placed, rather than recomputing it from scratch. This optimization is
  deferred for now.
- **New Rescore extension point**: Once group-aware plugins become signable, a dedicated `Rescore`
  plugin interface can be introduced to handle related-node score updates correctly. Plugins would
  return raw scores for all affected nodes; the framework combines them with cached raw scores for
  unaffected nodes and runs `NormalizeScore` on the full set. See [Alternatives](#alternatives) for
  the full design.

## Infrastructure Needed (Optional)

<!--
Use this section if you need things from the project/SIG. Examples include a
new subproject, repos requested, or GitHub details. Listing these here allows a
SIG to get the process for these resources started right away.
-->
