# Role of Sinkhorn Iteration in Needle 2's Routing Mechanism

> Discover how Sinkhorn iteration in Needle 2 converts similarity scores to doubly-stochastic matrices for differentiable load balancing and hard routing decisions.

- Repository: [Cactus Compute, Inc./needle](https://github.com/cactus-compute/needle)
- Tags: internals
- Published: 2026-09-11

---

**Needle 2 uses Sinkhorn iteration to convert token-expert similarity scores into doubly-stochastic assignment matrices, enabling differentiable load balancing before generating final hard routing decisions via argmax.**

Needle 2 introduces a modular architecture where discrete token-to-expert assignments must remain differentiable for end-to-end training. The Sinkhorn-Knopp algorithm solves this by projecting routing logits onto the set of doubly-stochastic matrices, ensuring balanced workload distribution across expert sub-networks. According to the cactus-compute/needle source code, this mechanism is implemented in the `Router` class within [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py).

## The Token-to-Expert Assignment Problem

Modern mixture-of-experts (MoE) architectures route input tokens to specialized sub-networks, or *experts*, to improve computational efficiency. This routing presents a discrete optimization challenge: each token must assign to exactly one expert, yet the assignment must remain differentiable to allow gradient-based learning.

In Needle 2, this problem is framed as a balanced assignment task. Without constraints, naive routing causes **expert collapse**, where popular experts receive excessive tokens while others remain idle. The Sinkhorn iteration enforces **load balancing** by driving the assignment matrix toward uniform marginal distributions.

## How Sinkhorn Iteration Works in Needle 2

The Sinkhorn algorithm transforms raw similarity scores into a soft assignment matrix through iterative normalization. In [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py), the `Router` class implements this as a four-stage pipeline:

1. **Compute similarity matrix** – Lines 45-55 compute `router_logits` using learned projections to generate raw affinity scores between tokens and experts.

2. **Exponentiate and initialize** – The logits are exponentiated to produce a strictly positive matrix suitable for entropy-regularized optimal transport.

3. **Iterative normalization** – Lines 57-68 apply the `sinkhorn` function, performing 3-5 alternating row and column normalizations. This projects the matrix onto the **Birkhoff polytope** of doubly-stochastic matrices, where each row and column sums to 1.

4. **Hard assignment** – Lines 70-73 execute `torch.argmax` on the rows of the resulting matrix to convert soft probabilities into discrete expert indices.

This process maintains differentiability through the normalization steps while the final `argmax` provides the discrete routing required for expert selection.

## Implementation in needle/model/architecture.py

The core routing logic resides in the `Router` class, where the `sinkhorn` method handles the matrix normalization. The implementation uses PyTorch operations that preserve gradient flow:

```python
import torch
from needle.model.architecture import NeedleModel

# Initialize model with 8 experts

model = NeedleModel(num_experts=8, hidden_dim=512)
tokens = torch.randint(0, model.vocab_size, (1, 128))

# Forward pass returns hard routing indices

output, routing = model(tokens)
print(routing.shape)  # torch.Size([1, 128])

```

To inspect the soft assignment matrix before hardening:

```python
with torch.no_grad():
    logits = model.router.compute_logits(tokens)
    soft_assign = model.router.sinkhorn(logits)
    

# Verify doubly-stochastic property

print(soft_assign.sum(dim=1))  # Rows sum to 1

print(soft_assign.sum(dim=2))  # Columns sum to 1

```

The routing indices can be converted to one-hot format for masking expert outputs:

```python
expert_outputs = model.experts(tokens)  # (batch, seq, num_experts, dim)

routing_one_hot = torch.nn.functional.one_hot(routing, num_classes=8).float()
masked = torch.einsum('bse,bsn->bsen', expert_outputs, routing_one_hot)

```

## Why Sinkhorn Iteration Matters

The Sinkhorn-based routing in Needle 2 provides three critical advantages over alternatives like Gumbel-Softmax or straight-through estimators:

**Load balancing** – By enforcing doubly-stochastic constraints, the algorithm naturally equalizes token distribution across experts. This prevents the "rich get richer" phenomenon where a subset of experts dominates the computation.

**Differentiability** – Unlike discrete sampling methods, the Sinkhorn iterations are fully differentiable. Gradients flow back through the routing decisions to update the projection layers that generate `router_logits`.

**Training stability** – The soft assignment matrix reduces variance in gradient estimates during early training phases. This stabilization is crucial when scaling to large numbers of experts, where purely stochastic routing would introduce excessive noise.

## Summary

- Needle 2 routes tokens using a **Sinkhorn iteration** that projects logits onto doubly-stochastic matrices.
- The implementation resides in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py), specifically lines 45-73 of the `Router` class.
- **3-5 normalization iterations** balance token loads while maintaining gradient flow.
- Final routing uses `torch.argmax` to convert soft probabilities into hard expert assignments.
- This approach prevents **expert collapse** and stabilizes training in modular architectures.

## Frequently Asked Questions

### What is the Sinkhorn iteration used for in Needle 2?

The Sinkhorn iteration solves the optimal transport problem between tokens and experts, producing a balanced, differentiable assignment matrix. It ensures that each expert receives approximately equal tokens while keeping the routing operation trainable via backpropagation.

### How does Needle 2 ensure balanced expert assignment?

Needle 2 enforces balance through the doubly-stochastic constraint imposed by Sinkhorn normalization. By iterating between row and column normalization (typically 3-5 times), the algorithm drives the assignment matrix toward uniform marginal distributions, preventing any single expert from being overloaded.

### Is the routing mechanism in Needle 2 fully differentiable?

Yes, the Sinkhorn projection is fully differentiable, allowing gradients to flow from the final expert outputs back to the routing logits. Only the final `argmax` operation is non-differentiable, but gradients pass through the soft assignment matrix that precedes it.

### Where is the Sinkhorn algorithm implemented in the codebase?

The algorithm is implemented in the `Router` class within [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py). The `sinkhorn` method (lines 57-68) performs the iterative normalization, while `compute_logits` (lines 45-55) generates the initial similarity scores.