Glossary

Krum

Krum is a Byzantine-resilient aggregation rule that selects the single local update vector with the minimal sum of squared distances to its nearest neighbors, effectively filtering out outlier gradients.

Get in touch Learn more

Engineer reviewing vector database search results on laptop, embeddings visualization on screen, home office coding session.

BYZANTINE-RESILIENT AGGREGATION

What is Krum?

Krum is a Byzantine fault-tolerant aggregation rule for distributed machine learning that selects a single local model update as the global update, chosen for its proximity to a majority of other updates, effectively neutralizing malicious outliers.

Krum is a Byzantine-resilient aggregation rule that defends federated learning against adversarial or corrupted client updates. Rather than averaging all received vectors, the algorithm computes a score for each local update based on the sum of squared Euclidean distances to its n - f - 2 nearest neighbors, where n is the total number of clients and f is the estimated number of Byzantine nodes. The update with the minimal score is selected as the global model update, effectively filtering out outlier gradients that deviate from the consensus.

The theoretical guarantee of Krum ensures convergence to the true optimum even when up to f clients submit arbitrary malicious updates, provided the total number of clients satisfies 2f + 3 < n. This makes it particularly valuable in healthcare federated learning environments where compromised edge devices or adversarial institutions could attempt model poisoning attacks. Variants like Multi-Krum extend the algorithm by averaging the top m scoring updates to improve statistical efficiency while maintaining Byzantine resilience.

Byzantine-Resilient Aggregation

Key Features of Krum

Krum is a foundational Byzantine fault-tolerant aggregation rule that selects a single local update vector as the global model, based on its proximity to a majority of honest updates. It effectively filters out malicious or corrupted gradients without requiring prior knowledge of the attacker's strategy.

Minimal Sum of Squared Distances

Krum operates by computing the pairwise squared Euclidean distances between all submitted local update vectors. For each vector, it sums the distances to its n − f − 2 closest neighbors, where n is the total number of clients and f is the maximum number of Byzantine nodes. The vector with the smallest total distance is selected as the global model update. This geometric approach assumes that honest updates cluster together in the parameter space, while Byzantine updates appear as outliers.

Byzantine Fault Tolerance Guarantee

Krum provides formal convergence guarantees under the assumption that the number of Byzantine workers f satisfies 2f + 2 < n. The algorithm is proven to converge to a region around the optimal solution even when up to f clients submit arbitrary, malicious, or corrupted gradients. This makes Krum particularly suitable for adversarial federated learning environments where client compromise is a realistic threat model.

Single-Vector Selection Mechanism

Unlike Federated Averaging, which computes a weighted mean of all updates, Krum selects exactly one local update as the global model for that round. This design choice provides strong robustness but can discard useful information from other honest clients. The selected vector is guaranteed to be among the n − f honest updates, effectively ignoring all potential Byzantine contributions without requiring explicit detection or filtering heuristics.

Multi-Krum Variant

To address the information loss from selecting a single vector, Multi-Krum extends the algorithm by selecting the m vectors with the smallest distance scores and averaging them. The selection criterion is applied iteratively: after choosing the best vector, it is removed from the candidate pool, and the process repeats. Multi-Krum retains Byzantine resilience while leveraging more honest updates, often achieving faster convergence and higher final accuracy than single-vector Krum.

Computational Complexity

Krum has a computational complexity of O(n² · d), where n is the number of clients and d is the dimensionality of the model. This quadratic scaling arises from computing all pairwise distances between update vectors. For large models with millions of parameters, this can become a bottleneck. Practical implementations often use dimensionality reduction or random projections to approximate distances efficiently, trading a small amount of precision for significant speedups.

Assumptions and Limitations

Krum relies on the critical assumption that honest gradients are concentrated around the true gradient, while Byzantine gradients are arbitrarily far. In highly non-IID settings common in healthcare federated learning, honest updates from different clinical sites may naturally diverge, violating this clustering assumption. Additionally, Krum requires the server to know the maximum number of Byzantine nodes f in advance, which may not be known in real-world deployments.

BYZANTINE FAULT TOLERANCE COMPARISON

Krum vs. Other Byzantine-Robust Aggregators

A technical comparison of Krum against alternative Byzantine-resilient aggregation rules for defending federated learning against malicious or corrupted client updates.

Feature	Krum	Trimmed Mean	Median
Core mechanism	Selects single vector with minimal sum of squared distances to n−b−2 nearest neighbors	Coordinate-wise removal of extreme values before averaging	Coordinate-wise median of all submitted updates
Byzantine tolerance threshold	Up to b < (n−2)/2 malicious clients	Up to b < n/2 malicious clients	Up to b < n/2 malicious clients
Output type	Single local update vector	Averaged vector of trimmed coordinates	Median vector of coordinates
Dimensionality sensitivity	High; squared Euclidean distance degrades in high dimensions	Low; operates coordinate-wise independently	Low; operates coordinate-wise independently
Computational complexity	O(n²·d) per round	O(n·d·log n) per round	O(n·d) per round
Convergence guarantee under strong convexity	Linear convergence to within δ of optimum	Linear convergence to optimum	Linear convergence to optimum
Handles non-IID client data
Vulnerable to 'a little is enough' attack

KRUM AGGREGATION

Frequently Asked Questions

Clear answers to common technical questions about the Krum Byzantine-resilient aggregation rule, its selection mechanism, and its role in securing federated learning against adversarial nodes.

Krum is a Byzantine-resilient aggregation rule for distributed machine learning that selects a single local model update vector as the global update, rather than computing an average. It operates by calculating the sum of squared Euclidean distances from each candidate update to its n - b - 2 closest neighbors, where n is the total number of clients and b is the estimated number of Byzantine adversaries. The update with the minimal distance score is chosen as the global model's direction. This majority-based selection mechanism inherently filters out outlier gradients submitted by malicious or faulty nodes, as adversarial updates will be geometrically distant from the dense cluster of honest contributions. The algorithm assumes that honest updates are concentrated in a tight cluster, while Byzantine updates lie outside this region, making Krum particularly effective when the proportion of adversaries is below a theoretical threshold.

Enabling Efficiency, Speed & Accuracy

Intelligent Analysis, Decision & Execution

We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.

Talk to Us

Search across company data

Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.

Useful when people spend too long searching or get different answers from different systems.

Enterprise searchRAGPermissions

Automate internal workflows

Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.

Useful when repetitive work moves across multiple tools and teams.

AI agentsWorkflow automationGovernance

Add AI to products and internal tools

Build assistants, guided actions, or decision support into the software your team or customers already use.

Useful when AI needs to be part of the product, not a separate tool.

AI integrationDecision supportModel routing

BYZANTINE-RESILIENT AGGREGATION

Related Terms

Explore the ecosystem of robust aggregation algorithms and defensive techniques that complement Krum in securing federated learning against adversarial clients and corrupted updates.

Byzantine Fault Tolerance (BFT) Aggregation

A class of robust aggregation rules ensuring global model convergence despite arbitrary or malicious client updates. Krum is a foundational BFT algorithm that selects the single most representative gradient vector.

Assumes up to f Byzantine nodes out of n total clients
Krum requires n > 2f + 3 for theoretical guarantees
Alternative BFT rules include Multi-Krum, Bulyan, and Median

Trimmed Mean Aggregation

A coordinate-wise robust technique that discards extreme values for each model parameter before averaging. Unlike Krum's vector-level selection, trimmed mean operates independently on each dimension.

Removes k largest and k smallest values per coordinate
Effective against omniscient adversaries manipulating specific parameters
Often combined with Krum in hybrid defenses for layered protection

Multi-Krum

An extension of Krum that selects multiple candidate vectors and averages them, rather than relying on a single update. Improves statistical efficiency while maintaining Byzantine resilience.

Selects m vectors with lowest Krum scores
Reduces variance compared to single-vector Krum
Requires n > 2f + 3m for theoretical guarantees

Bulyan

A two-phase aggregation protocol that first applies a Byzantine-resilient selection (like Krum) to filter candidates, then performs trimmed mean on the selected set. Combines the strengths of both approaches.

Phase 1: Select θ vectors using Krum or Multi-Krum
Phase 2: Coordinate-wise trimmed mean on selected set
Provides stronger guarantees against high-dimensional attacks

Gradient Clipping

A defensive pre-processing step that constrains the L2 norm of local model updates before aggregation. Prevents adversaries from submitting arbitrarily large gradients designed to dominate Krum's distance calculations.

Clips gradients to a maximum norm threshold C
Mitigates model poisoning and exploding gradient attacks
Often used alongside Krum as a first line of defense

Median Aggregation

A coordinate-wise Byzantine-resilient rule that takes the median value of each parameter across all client updates. Simpler than Krum but less effective against sophisticated attacks targeting multiple coordinates.

Computationally lightweight compared to Krum's pairwise distance calculations
Breaks down under omniscient attacks manipulating many parameters
Often used as a baseline for evaluating Krum's performance

About the author

Prasad Kumkar

CEO & MD, Inference Systems

Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.

His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.

Limited slotsGet a Free AI Consultation

How We Work

Custom AI workflows for your Business

One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.