Dust: Zeroth-Order Optimization Trains Transformers Without Backpropagation

Background: Challenging Backpropagation's Monopoly

Backpropagation has been the sole mainstream algorithm for training neural networks for years, shaping architectures, optimizers, and even GPU hardware. However, it requires the entire network to be differentiable, excluding non-differentiable modules, discrete computations, and external programs from the training loop. Researchers have long explored alternatives that could work without gradients, especially as compute becomes cheaper.

Why Challenge Backpropagation?

Q Labs frames their work as a tribute to Rich Sutton's "Bitter Lesson": methods relying on clever inductive biases (like differentiability and backpropagation) eventually lose to general, compute-hungry brute-force search. They analogize to AlphaGo Zero — human-guided versions learn faster initially, but pure self-play surpasses them with sufficient compute. Differentiability and backpropagation may be "good biases for the low-compute era" that restrict the space of trainable architectures in the high-compute era. They further speculate that gradient methods may not sufficiently explore the loss landscape, and a search-based, more flexible credit assignment algorithm could be key to better generalization.

Dust's Core Idea: Virtual Population in Activation Space

Dust moves perturbation from weight space (traditional evolution strategies) to activation space, exploiting the token dimension for massive parallelism.

Perturbation Mechanism

For a linear layer output yₜ = Wxₜ, Dust adds per-token Gaussian noise: yₜ → yₜ + σaₜ, where σ controls perturbation magnitude and aₜ ~ N(0, I). Each token becomes a "virtual population member" experiencing a slightly different effective model, without copying or modifying weights. A single forward pass evaluates thousands of virtual individuals in parallel along the token dimension, unlike traditional ES which requires separate forward passes per population member.

Credit Assignment with Decay

Transformer tokens have dependencies, especially under causal attention. Dust assigns credit using a decayed reward: rₜ = Σₛ γ^{s-t} cₛ, where cₛ is the loss improvement at token s and γ controls future token contribution weight. A token's perturbation earns extra reward if it improves subsequent predictions.

Gradient Estimation

Dust computes a weighted average of sampled noises with their rewards to estimate the output error signal ĝₜ, then forms the weight update via outer product with the layer input xₜ: ΔW ∝ Σₜ ĝₜ xₜᵀ. This estimates gradients without backpropagation's chain rule, using only forward-pass loss changes.

Avoiding Interference Between Simultaneous Perturbations

Multiple layers and tokens perturbed simultaneously create attribution ambiguity. Dust addresses this with three optimizations:

Layer-wise perturbation with cached clean activations: Different layer types perturb separately, caching unperturbed intermediate results to avoid redundant forward passes.

Attention-module-specific rewards: For Query, Key, Value, and Gate components, rewards are based on perturbation-induced attention output changes combined with estimated output error signals, not raw token loss.

Output head perturbation on cached logits: Perturbations applied directly to cached logits, recomputing only cross-entropy loss, enabling cheap population scaling at the final layer.

Hyperparameter search tunes perturbation strength, sampling ratio, and credit assignment range per layer.

Experimental Results

Experiments on FineWeb dataset compare Dust with backpropagation (SGD/Adam) and EGGROLL (prior low-rank ES).

Sample Efficiency vs. EGGROLL

Dust with 64 perturbation samples outperforms EGGROLL with 16,384 population members — a 256× efficiency gain — confirming activation-space perturbation improves sampling efficiency.

Scaling to Larger Models

Dust effectively trains models scaling ~120× from 2M to 243M parameters. At larger population sizes, 38M and 243M parameter models achieve lower test loss than the 2M model, and larger models benefit more from increased sampling. This challenges the conventional view that zeroth-order methods fail to scale to large networks.

Gradient Alignment with Backpropagation

As sampling scale increases, Dust's estimated gradient direction converges toward the true backpropagation gradient, even after extended training, indicating Dust can continuously extract useful gradient signals by expanding the virtual population.

Competitive Performance

At certain compute budgets, Dust matches or exceeds backpropagation performance. However, the largest experiments reach only 243M parameters and 20M tokens — far from industrial trillion-token pretraining. Some "superior" results come from curve-fitting extrapolation, not direct training runs.

Independent Replication and Caveats

SOTAAZ Lab's replication confirms Dust's basic results under the paper's single-epoch SGD comparison, but finds the gap to backpropagation is small with no clear advantage. When backpropagation uses a better optimizer or trains for multiple epochs on the same data, it pulls ahead decisively at far lower compute cost. The replication concludes Dust's significance lies in proving zeroth-order methods can work for Transformer pretraining, not in replacing backpropagation today.

Q Labs Research Trajectory

Q Labs (investors include Jeff Dean) pursues a consistent agenda: "If we give models more compute instead of more data, can they learn better?" Their prior work includes NanoGPT Slowrun (fixed data budget, optimize data efficiency) and q0 (model populations exploring and combining predictions on same data, reporting ~12.9× data efficiency gain). Dust pushes further: replacing the training algorithm itself to see if more compute yields new returns. Founders Samip Dahal (Replit Ghostwriter) and Akshay Vegesna (Nuro perception) bring applied ML experience. The team emphasizes open science: paper followed by code and public "Noise speedrun" competition forbidding backpropagation.

Current Status and Outlook

Dust remains far more expensive than backpropagation. Community optimization on the Noise speedrun benchmark reduced time-to-target from ~1.76 hours to 1.6 seconds (~4000× speedup) at 10M tokens targeting validation loss 4.2, but this compares against early Dust+Adam, not backpropagation, and many speedup tricks may not scale. The critical questions remain: at larger models, longer training, and lower target losses, can perturbation-based updates still work, and at what compute cost? Dust has demonstrated feasibility; subsequent experiments will determine how far this path extends.