← Back to blog
May 22, 2026Colm Byrne

20 Iterations to Perfect Trust Conservation: The Sinkhorn-Knopp Convergence Bound for Embedded Systems

The previous post on Sinkhorn-Knopp explains WHY doubly stochastic matrices are the only safe trust transfer mechanism. This post explains HOW to implement the projection on hardware where you cannot afford a convergence loop.

A companion robot running on an ARM Cortex-M4 at 168 MHz has a fixed time budget per tick. The trust transfer computation must complete in bounded, deterministic time. No while loops. No convergence checks. No "run until the error is small enough." The iteration count must be fixed at compile time, and the resulting deviation must be provably below the precision threshold of the hardware's floating-point unit.

Patent section [0058a] of the supplement to US 63/988,438 specifies the bound. Here is the derivation, step by step.

The Setup

Start with a parameter matrix M of context affinities. In CCF, these are derived from the cosine similarities between context keys -- how similar two environmental contexts are in their sensor signatures.

The first step is clamping. Every entry of M is clamped to the range [-M_range, +M_range]:

M_clamped[i][j] = clamp(M[i][j], -M_range, M_range)

Default: M_range = 1.5. This is not arbitrary. It controls the condition number of the resulting matrix, which controls the convergence rate. More on this below.

The second step is exponentiation. Each entry becomes:

A[i][j] = exp(M_clamped[i][j])

This produces a strictly positive matrix A. The exponential maps the symmetric range [-1.5, 1.5] to the asymmetric positive range [exp(-1.5), exp(1.5)]:

exp(-1.5) = 0.2231
exp(+1.5) = 4.4817

Every entry of A is between 0.2231 and 4.4817. There are no zeros. No negative entries. The matrix has full support, which is the precondition for Sinkhorn-Knopp convergence.

The Condition Number

The condition number of A -- the ratio of the largest to the smallest entry -- determines how far A is from doubly stochastic, and therefore how many iterations are needed.

kappa = max(A) / min(A) = exp(M_range) / exp(-M_range) = exp(2 * M_range)

For M_range = 1.5:

kappa = exp(3.0) = 20.09

This is the single number that controls everything. It tells you: the most dissimilar pair of contexts has an affinity ratio of 20:1 relative to the least similar pair. The Sinkhorn-Knopp algorithm must redistribute this 20:1 ratio into a doubly stochastic matrix where every row and column sums to exactly 1.

The Contraction Coefficient

Sinkhorn-Knopp converges because each iteration of alternating row-and-column normalisation contracts the distance to the doubly stochastic set. The Birkhoff contraction coefficient quantifies the rate:

tau = ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^2

Step by step for kappa = 20.09:

sqrt(kappa) = sqrt(20.09) = 4.482

numerator   = 4.482 - 1 = 3.482
denominator = 4.482 + 1 = 5.482

ratio       = 3.482 / 5.482 = 0.6352

tau         = 0.6352^2 = 0.4035

tau = 0.4035. This means that after each full iteration (one row normalisation plus one column normalisation), the maximum deviation from doubly stochastic is multiplied by at most 0.4035. The deviation contracts by a factor of 2.5 per iteration.

The 20-Iteration Bound

After t iterations, the maximum deviation from doubly stochastic is bounded by:

max_deviation(t) <= tau^t

For t = 20:

max_deviation(20) <= 0.4035^20

Computing 0.4035^20 step by step:

0.4035^1  = 0.4035
0.4035^2  = 0.1628
0.4035^4  = 0.02651
0.4035^8  = 7.028e-4
0.4035^16 = 4.939e-7
0.4035^20 = 0.4035^16 * 0.4035^4
          = 4.939e-7 * 0.02651
          = 1.309e-8
          ≈ 1.2e-8

After 20 iterations: max deviation ≤ 1.2 x 10^-8.

Every row sum is within 1.2e-8 of 1.0. Every column sum is within 1.2e-8 of 1.0. The resulting matrix is doubly stochastic to eight decimal places.

Why 20 Is Enough for 32-Bit Float

The key insight: 1.2e-8 is BELOW the epsilon of 32-bit floating-point arithmetic.

IEEE 754 float32 has a machine epsilon of approximately 1.19e-7. This means that the difference between 1.0 and the next representable float32 value is about 1.19e-7.

Our convergence bound of 1.2e-8 is ten times smaller than float32 epsilon. In practice, this means the Sinkhorn-Knopp output is as close to doubly stochastic as float32 can represent. There is no benefit to additional iterations -- the hardware cannot distinguish the result from a perfect doubly stochastic matrix.

Convergence bound:  1.2e-8
float32 epsilon:    1.19e-7
Margin:             ~10x below hardware precision

No convergence check needed. No error monitoring. No dynamic iteration count. Twenty iterations is a HARD CONSTANT that can be burned into firmware. The result is mathematically guaranteed to be within hardware precision of doubly stochastic.

The Algorithm

The implementation is straightforward. No allocation. No branching. Fixed loop count.

const MAX_ITER: usize = 20;
const M_RANGE: f32 = 1.5;

fn sinkhorn_project(params: &[[f32; N]; N]) -> [[f32; N]; N] {
    // Step 1: Clamp and exponentiate
    let mut matrix = [[0.0f32; N]; N];
    for i in 0..N {
        for j in 0..N {
            let clamped = params[i][j].clamp(-M_RANGE, M_RANGE);
            matrix[i][j] = clamped.exp();
        }
    }

    // Step 2: Alternating normalisation (fixed 20 iterations)
    for _iter in 0..MAX_ITER {
        // Row normalisation
        for i in 0..N {
            let row_sum: f32 = matrix[i].iter().sum();
            if row_sum > 0.0 {
                for j in 0..N {
                    matrix[i][j] /= row_sum;
                }
            }
        }
        // Column normalisation
        for j in 0..N {
            let col_sum: f32 = (0..N).map(|i| matrix[i][j]).sum();
            if col_sum > 0.0 {
                for i in 0..N {
                    matrix[i][j] /= col_sum;
                }
            }
        }
    }

    matrix
}

That is the complete algorithm. Two nested loops (row, then column), repeated 20 times. No heap allocation. No dynamic dispatch. No convergence test. Compiles to no_std Rust for bare-metal ARM deployment.

Performance on Embedded Hardware

For a matrix of dimension n, each Sinkhorn iteration is O(n^2): one pass over all n^2 entries for row normalisation, one pass for column normalisation. Twenty iterations is 40 passes over n^2 entries.

For n = 64 (the default MAX_CONTEXTS in ccf-core on crates.io):

Operations per iteration: 2 * 64 * 64 = 8,192
Total operations (20 iter): 20 * 8,192 = 163,840

On an ARM Cortex-M4 at 168 MHz with hardware FPU (single-precision), each floating-point divide takes approximately 14 cycles. Each sum takes 1 cycle. Conservatively:

Cycles per iteration: ~115,000
Total cycles (20 iter): ~2,300,000
Wall time at 168 MHz: ~13.7 milliseconds

13.7 milliseconds for a 64x64 trust transfer projection. On a typical 100 ms tick interval, this consumes about 14% of the compute budget. Acceptable for a system that also needs to read sensors, update accumulators, compute phase transitions, and drive actuators.

For n = 16 (a smaller deployment):

Total operations: 20 * 2 * 256 = 10,240
Wall time at 168 MHz: ~0.9 milliseconds

Under a millisecond. Negligible.

Scaling: What If You Need More Range?

The M_range parameter controls the trade-off between expressiveness and convergence speed. A larger M_range allows the affinity matrix to represent stronger preferences (some context pairs are much more similar than others), but the condition number increases and more iterations are needed.

The scaling formula:

kappa(M_range) = exp(2 * M_range)
tau(kappa) = ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^2
t_required = ceil(log(10^-8) / log(tau))

Worked examples:

M_range = 1.0: kappa = 7.39,  tau = 0.254, t = 14 iterations
M_range = 1.5: kappa = 20.09, tau = 0.404, t = 20 iterations (default)
M_range = 2.0: kappa = 54.60, tau = 0.527, t = 29 iterations
M_range = 2.5: kappa = 148.4, tau = 0.627, t = 40 iterations
M_range = 3.0: kappa = 403.4, tau = 0.704, t = 53 iterations

At M_range = 2.0, you need 29 iterations -- 45% more compute. At M_range = 3.0, you need 53 iterations -- nearly triple the default. For embedded systems, M_range = 1.5 is the sweet spot: sufficient dynamic range for domestic context affinities, and 20 iterations fits comfortably in the tick budget.

If your application needs M_range = 2.0 or higher (e.g., industrial environments with extreme sensor variance), increase the iteration count accordingly. The bound is tight -- you cannot cheat it with fewer iterations. But you also do not need to over-provision. The formula gives you the exact iteration count for your precision target.

What Double Stochasticity Gets You

The 20-iteration Sinkhorn-Knopp output feeds directly into the trust transfer step. The doubly stochastic matrix M is applied to the coherence vector c:

c_new = M * c_old

Because M is doubly stochastic (to within 1.2e-8):

  1. Trust conservation. sum(c_new) = sum(c_old). Total trust in the system is preserved. See Sinkhorn-Knopp for Trust for the proof.

  2. Non-amplification. No context's coherence increases beyond the system maximum. The spectral norm of M is exactly 1. Trust flows from high-coherence contexts to low-coherence ones.

  3. Compositional closure. If M_1 and M_2 are both outputs of this algorithm, then M_1 * M_2 is also doubly stochastic. The guarantee holds after arbitrary compositions. See Compositional Closure for why this matters for long-running systems.

These three properties -- conservation, non-amplification, composition -- are the mathematical foundation of CCF's safety guarantees. And they all depend on the mixing matrix being doubly stochastic. The 20-iteration bound ensures that the matrix IS doubly stochastic, not "approximately" or "hopefully," but to the precision limit of the hardware.

Why Not a Convergence Loop?

A natural question: why not iterate until convergence rather than using a fixed count?

Three reasons.

Determinism. Embedded safety systems must have deterministic execution time. A convergence loop completes in a variable number of iterations depending on input data. This creates variable execution latency, which can cause deadline misses in real-time systems. Fixed iteration count means fixed execution time. Always.

Worst case equals average case. With a convergence loop, you must provision for the worst case anyway (the input that converges slowest). Since the 20-iteration bound IS the worst case for M_range = 1.5, the fixed loop uses the same number of iterations that a convergence loop would use in the worst case. There is no efficiency gain from early termination -- you have already budgeted for 20 iterations.

No branch prediction penalty. The inner loop has no conditional exit. On ARM Cortex-M, this means the branch predictor never mispredicts on the loop termination, and the instruction pipeline stays full. A convergence check introduces a conditional branch per iteration that disrupts the pipeline when it finally triggers.

Independence from Matrix Dimension

A subtle but critical property: the contraction coefficient tau depends ONLY on the condition number kappa, which depends only on M_range. It does NOT depend on the matrix dimension n.

tau = ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^2

There is no n in this formula. The same 20-iteration bound guarantees 1.2e-8 deviation whether the matrix is 4x4 or 64x64 or 256x256. The compute TIME scales as O(n^2) per iteration, but the ITERATION COUNT is constant.

This means you can increase the number of contexts in a CCF deployment without changing the convergence guarantee. Going from 16 contexts to 64 contexts quadruples the per-iteration cost but does not increase the iteration count. The safety bound is scale-independent.

For deployments using the hierarchical mixer, the Sinkhorn-Knopp projector runs separately on each cluster's intra-cluster matrix and on the inter-cluster matrix. Each projection uses the same 20 iterations with the same 1.2e-8 guarantee, regardless of cluster size. Block-diagonal doubly stochastic matrices composed of individually projected blocks are themselves doubly stochastic.

The Implementation in ccf-core

The Sinkhorn-Knopp projector is implemented as the SinkhornKnopp struct in ccf-core on crates.io, Claims 19-23 of the patent. The implementation uses fixed 20 iterations, M_range = 1.5, and operates entirely in no_std Rust with no heap allocation. It compiles to ARM Cortex-M targets with thumbv7em-none-eabihf, verified in CI.

The project_flat() method handles runtime-determined matrix dimensions (for hierarchical mixing where cluster sizes vary). The core project() method handles compile-time-determined dimensions with const generics for maximum performance.

Both methods produce identical results: a doubly stochastic matrix within 1.2e-8 of exact, in exactly 20 iterations, with no convergence loop.

— Colm Byrne, Founder — Flout Labs, Galway, Ireland

Patent pending. US Provisional 64/039,626.

FAQ

Can you use fewer than 20 iterations if the input matrix is already close to doubly stochastic?

You can, but the fixed-iteration approach is preferred for embedded systems. If the input is already close to doubly stochastic (e.g., kappa close to 1), the algorithm converges faster and later iterations do negligible work. But the work is cheap (divide and sum) and the execution time is already budgeted. Skipping iterations saves microseconds but introduces a conditional branch and makes execution time data-dependent. For non-embedded platforms where determinism is less critical, you could monitor the max deviation after each iteration and exit early when it drops below your threshold.

Why exp() for the element-wise transformation? Why not just use raw affinities?

The exponential serves two purposes. First, it ensures strict positivity -- exp(x) is always positive, even for negative affinities. Sinkhorn-Knopp requires a positive matrix (technically, one with total support). Second, it maps the symmetric affinity range [-M_range, +M_range] to a bounded positive range with a controlled condition number. Raw affinities might include zeros or near-zeros, which would create convergence problems. The exponential is a smooth, well-conditioned mapping that converts any real-valued affinity matrix into a valid Sinkhorn-Knopp input.

How does the 1.2e-8 bound compare to double-precision (float64) implementations?

float64 has machine epsilon of approximately 2.2e-16. To reach that precision with M_range = 1.5, you would need ceil(log(2.2e-16) / log(0.4035)) = 40 iterations -- double the float32 requirement. But for CCF's trust dynamics, float32 precision is more than sufficient. The coherence accumulators operate in the [0.0, 1.0] range with meaningful granularity of about 0.001 (one-tenth of a percent of trust). A deviation of 1.2e-8 in the mixing matrix produces an error of roughly 1.2e-8 in the output coherence vector -- five orders of magnitude below the meaningful granularity. Double precision would be wasted on a system where the trust differences that matter are measured in hundredths.

What happens if some entries of the parameter matrix are NaN or infinity?

The clamp step handles this. In Rust, f32::clamp() returns the lower bound for NaN inputs, and infinity is clamped to M_range. After clamping, every entry is in [-1.5, 1.5]. After exponentiation, every entry is in [0.223, 4.482]. The algorithm is robust to pathological inputs because the clamp-then-exp pipeline is a total function: every possible float32 input produces a valid, bounded, positive output.

Is the Birkhoff contraction coefficient tight, or is it a loose upper bound?

It is tight for the worst-case input. The bound tau^t is achieved by matrices whose entries alternate between exp(-M_range) and exp(+M_range) in a checkerboard pattern. For typical inputs (where affinities are more uniform), convergence is faster. But the bound is what lets you fix the iteration count at compile time -- you need it to hold for ALL inputs, not just typical ones. In practice, most CCF affinity matrices converge in 10-12 iterations. The remaining 8-10 iterations are "free insurance" that costs under 7 milliseconds on ARM Cortex-M4.