In federated learning, a central server trains one model from updates sent by many remote devices. Two problems hit it at once. Some devices are slow, called stragglers, so waiting for everyone stalls training. Some devices are Byzantine, meaning faulty or malicious, and they send corrupted updates. Today's defenses that handle both, such as clustering arrivals and down-weighting late ones, are hand-written rules with hand-picked constants. Those rules miss a simple attack. A malicious device does no real computation, so it can always reply first. If the server keeps only the fastest replies, attackers fill the accepted set.
We propose to search for the server's aggregation rule as executable code. A code-writing language model acts as the mutation operator, in the style of LLM-driven program search. Candidate rules are scored in a cheap synthetic arena of simulated clients with random delays and attackers. The attackers' strategies, including when they choose to arrive, evolve against the rules at the same time. The rule is restricted to quantities that do not depend on model size: norms, cosines, arrival times, staleness, and per-client frequency. That restriction lets a rule found on 50-dimensional toy problems run unchanged, with no retraining and no server-side data, on real federated training of image and language models. The bet is the same one that lets learned black-box optimizers transfer zero-shot across dimensions. Here the invariant structure is the geometry and timing of honest versus adversarial updates, not the shape of a loss landscape.
Core Claim
A robust asynchronous aggregator can be found once, in a synthetic arena, and then deployed zero-shot. The arena must co-evolve attackers that control both what they send and when they arrive. The aggregator must be a short, auditable program over dimension-free features of the update buffer. We claim such a program will match or beat hand-designed asynchronous Byzantine defenses in three respects: accuracy under attacks it never saw in training, wall-clock time to a target accuracy, and accuracy on slow clients' data. We further claim it will survive a white-box attack optimized against its final code. The search space is restricted, and the result is code a person can read, so we can check by inspection that the rule does not secretly depend on dimension or dataset.
Where this sits
Three systems already combine straggler tolerance with Byzantine robustness, and all three use fixed rules. These are the closest prior work and the source of our baselines.
Kardam filters asynchronous gradients with a Lipschitz-style check and a cap on how often one worker may update. Its Theorem 2 shows that without some frequency bound, a single fast attacker makes asynchronous Byzantine learning impossible. This result constrains our design: frequency history must be an input to the rule.
Catalyst waits for a quorum of $2f+1$ arrivals and clusters them by angle with HDBSCAN. It then re-admits late updates with a hand-chosen staleness decay. Its quorum can stall when arrivals are sparse.
dSTAR aggregates the fastest $k$ workers and filters them against an anchor built from a server validation set. It uses a fixed $k$ and depends on that server data.
None of the three treats arrival time as something an attacker controls, which is the weakness our arena targets.
Our method comes from two other lines of work. FunBO and EvolCAF evolve Python acquisition functions for Bayesian optimization on low-dimensional synthetic problems and transfer them to harder ones. Their acknowledged cost is that each candidate must be run on full optimization trajectories. Our arena makes that cheap, because one simulated federated run on quadratics takes milliseconds. POM and RLDE-AFL show that optimizers which see only rankings, fitness changes, and population statistics transfer across dimension, while optimizers that see raw coordinates do not. We apply the same discipline to the server's inputs.
Three papers on attacks and defenses shape the design. A Little Is Enough and Fang et al. show that any fixed rule can be targeted by an attacker optimized against it. This is the main threat to a learned rule, and it is why attackers co-evolve and why we finish with a white-box attack on the final program. STPA shows that comparing each update with the running average direction of past updates (the momentum) helps against stealthy attacks, so momentum alignment is one of our primitives.
Research Program
The arena. Each episode simulates $N$ clients, with $N$ between 20 and 100. Each client has a quadratic or logistic loss of dimension 10 to 100. The clients' optima are spread apart to mimic devices holding different kinds of data. Compute delays are drawn from one of several families: exponential (the model analyzed in Slow and Stale Gradients Can Win the Race), heavy-tailed, or bimodal. In some episodes, client speed is correlated with which data a client holds, so that ignoring slow clients biases the model. Between 0% and 40% of clients are Byzantine.
The attackers. Attackers are programs from a second evolving population. Each one chooses an update vector, seeded from ALiE-style, Fang-style, sign-flip, and backdoor-style templates. It also chooses when to arrive and how often.
The rule. An aggregator program sees the current buffer of arrived updates through fixed primitives. These are pairwise cosines, norms, alignment with the global momentum, the coordinate-wise median of the buffer, staleness, time since arrival, and each client's recent update frequency. The program returns two things: whether to update now or keep waiting, and a weight for each buffered update. Every primitive outputs scalars, so the program is dimension-free by construction.
The fitness. Fitness is worst-case progress per unit of wall-clock time:
$$F(A) = \min_{B \in \mathcal{B}} \; \mathbb{E}_{e}\left[ \frac{L_e(\theta_0) - L_e(\theta^{A,B}_{T})}{L_e(\theta_0)} \right]$$
Here $A$ is the aggregator program, $\mathcal{B}$ is the current attacker population, $e$ ranges over sampled episodes, $L_e$ is the honest clients' average loss, and $\theta^{A,B}_T$ is the model after a fixed wall-clock budget $T$. Attackers are scored by the negative of the same quantity. Measuring over a wall-clock budget rather than over iterations is the error-per-second view of Dutta et al.
The search. A code language model proposes mutations and crossovers of aggregator programs, starting from Catalyst-like and Kardam-like seeds. Programs that exceed an operation budget, measured in buffer-sized operations, are rejected, so the rule stays cheap at the server. We keep the best few programs and read them. We expect, and will check, that the search rediscovers a frequency cap, consistent with Kardam's impossibility result. We also expect it to learn some way of discounting early arrivals that agree suspiciously closely with each other. That second behavior would be the new mechanism.
Baselines
Plain asynchronous averaging. The naive reference point is asynchronous federated averaging with polynomial staleness decay and no filtering. Synchronous coordinate-wise median and Krum, which wait for every client, serve as the robust-but-slow reference. Both run on the same clients, delay traces, and attacks. They mark the floor for robustness and the ceiling for time per round. On CIFAR-10 under ALiE with 12 of 51 workers malicious, Krum falls from about 60% to 20.3% accuracy and Bulyan to 28.1% (A Little Is Enough).
Catalyst (strongest existing method). Catalyst is the strongest competitor because it is asynchronous, needs no server data, and re-uses stragglers. Those are the same constraints we impose. It reports 92% MNIST accuracy under gradient inversion, where other asynchronous methods diverged, and a backdoor success rate reduced to 0.5%. For non-IID CIFAR-10 the file gives only "up to 1.54x higher accuracy" than prior asynchronous methods, not an absolute number, so we will re-run it ourselves. Its quorum and decay constants get the same tuning budget as our search, measured in simulated-episode evaluations plus a matched number of short real-task runs.
Kardam and dSTAR. Kardam and dSTAR are run with their published rules. dSTAR reports 3.79 s per iteration versus 7.62 s for synchronous robust rules with 25 workers. It is given its server validation set, which our method is denied. We report that asymmetry rather than hide it.
What counts as beating them. We must exceed Catalyst's accuracy under held-out attacks on non-IID CIFAR-10 and WikiText-2 by a margin larger than seed variance. We must also match or beat its wall-clock time to target accuracy, and raise accuracy on the slowest clients' classes.
Ablations. Two ablations isolate the key ingredients. The first evolves aggregators against a fixed attack set instead of co-evolving attackers. The second gives attackers no control over arrival time. If either ablation matches the full method, the co-evolution or timing claim is false.
Why not just…?
Why not just tune Catalyst's or dSTAR's constants on the same arena? This is the most serious alternative. A good parametric family tuned by Bayesian optimization may capture most of the gain. We run it as a baseline with an equal evaluation budget. The parametric family includes quorum size, the decay exponent, the clustering threshold, a frequency cap, and an early-arrival penalty weight. If it matches the evolved programs, we will report that the gain comes from the arena and the attacker co-evolution, not from program search. That would still be a useful result, but a narrower one.
Why not train a neural aggregator, such as attention over the buffer, as POM does for populations? It could fit the arena as well as a program does. But a white-box attacker can differentiate through a network, and nobody can read its decision logic to confirm dimension-independence. We include it, fed the same features, and subject it to the same final adaptive attack. The prediction is that it degrades more under that attack. If it does not, the interpretability argument is the only remaining advantage of programs.
Why not just stack existing defenses: Catalyst clustering, STPA momentum checks, and a Kardam frequency cap? This hand-composed defense is a baseline. It shares Catalyst's quorum stall and has no defense against attackers that arrive early and agree with each other. The timing-hijack experiment below tests exactly this case.
Why not search directly on real federated tasks? Each candidate would need a full CIFAR-10 run, which is the upfront-cost problem FunBO and EvolCAF already report. Searching on the real task would also remove the zero-shot claim. We spend a small matched budget of real-task tuning only on the baselines' constants, so the comparison favors them.
Proposed Experiments and Decisive Checks
Transfer setup. Rules found in the arena are frozen and deployed on four tasks: non-IID CIFAR-10 and Fashion-MNIST with a small CNN or ResNet, MNIST, and WikiText-2 with a small transformer. Each task uses 25 to 100 clients and 20% to 40% Byzantine clients. Attacks include held-out ALiE, Fang-style Krum and median attacks, Empire, gradient inversion, label flipping, and backdoors. Delays come either from recorded heterogeneous-device traces or from the arena's delay families.
Metrics. We measure final accuracy, wall-clock time to a target accuracy, accuracy on the classes held mainly by the slowest decile of clients, backdoor success rate, and server time per update.
Check 1: timing hijack. 25% of clients are Byzantine and answer instantly. Fastest-$k$ rules then admit an attacker majority. The evolved rule must keep accuracy near the no-attack level while dSTAR-style selection fails.
Check 2: final adaptive attack. We run a Fang-style optimization against the final program's exact code, with knowledge of its constants. Accuracy loss must stay comparable to Catalyst's under its own adaptive attack.
Check 3: dimension sweep. We scale models over two orders of magnitude in parameter count. Performance should not drift, which tests whether the rule is truly dimension-free.
Check 4: straggler fairness. Client speed is correlated with label. The evolved rule must beat fastest-$k$ selection on slow-client accuracy without losing time to target.
Failure criterion. If held-out attacks, white-box attacks, or the dimension sweep erase the advantage over tuned Catalyst, the claim fails. We will say so.
References
- Asynchronous Byzantine Machine Learning
- Asynchronous Byzantine Federated Learning
- dSTAR: Straggler Tolerant and Byzantine Resilient Distributed SGD
- FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch
- Evolve Cost-Aware Acquisition Functions Using Large Language Models
- Pretrained Optimization Model for Zero-Shot Black Box Optimization
- Reinforcement Learning-based Self-adaptive Differential Evolution through Automated Landscape Feature Learning
- A Little Is Enough: Circumventing Defenses For Distributed Learning
- Local Model Poisoning Attacks to Byzantine-Robust Federated Learning
- Byzantine-robust Federated Learning through Spatial-temporal Analysis of Local Model Updates
- Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD