When Thread Count Becomes an Implicit Input: A Guide to Debugging Bit-Level Differences in FHE Ciphertexts

In FHE (Fully Homomorphic Encryption) inference tasks, using the same source code and the same input but changing the thread count from 4 to 8 can produce ciphertexts that differ at the bit level. This is not a floating‑point precision issue; it stems from randomness being an implicit function of execution order. Based on project practice, this article reveals the root cause, the direction of the fix that has been finalized, its current implementation status, and a reusable parallel‑debugging checklist.

1. Phenomenon: It Was Found by "Comparing Bytes", Not by "Looking at Errors"

If we only look at max|err|, everything appears normal—both the 4‑thread and 8‑thread results fall within the tolerance, and verify_layer reports PASS. They are simply "not identical", and max|err| was never designed to measure identity.

The discrepancy was discovered by byte‑by‑byte comparison:

u0_{t}_{h}.ct × 8 → BIT_IDENTICAL: 8 / 8 ← same thread count, same input Switch to a different thread count → bytes differ

The toolchain already has this capability: verify_layer -BitA u5 -BitB u5b -L 5 performs bit‑level comparison.

Lesson: If you never compare bytes, you will never know that your "reproducibility" only extends to "numerical closeness".

2. Root Cause: Three Lines of Code

The entire problem lies in these few lines (vllm_ckks.c):

c /* RNG (xorshift64*, prototype) / static _Thread_local uint64_t ckks_rng_state = 0x243F6A8885A308D3ull; / ← fixed constant */

static uint64_t ckks_rng_u64(void) { ... uint64_t x = ckks_rng_state; x ^= x >> 12; x ^= x << 25; x ^= x >> 27; ckks_rng_state = x; /* ← only advanced by its own thread */ return x * 0x2545F4914F6CDD1Dull; }

Two factors combine to cause the issue:

Consequently, every thread begins from the same seed and generates "the same" random stream; however, which thread generates how many values and to which object they are assigned is entirely determined by scheduling.

A concrete example: suppose an encryption requires 100 random coefficients. With 4 threads, each thread takes 25 (thread 0 gets 1‑25, thread 1 gets 26‑50, …). With 8 threads, each thread gets 12‑13. The random numbers assigned to a given logical object therefore differ between the two thread counts. The noise differs, and the ciphertext naturally differs.

"Different noise" is perfectly legitimate in homomorphic encryption—noise is inherently random as long as it stays within bounds. That is why no error is reported.

3. Why max|err| Never Reveals It

max|err| measures "the difference after decryption compared to the plaintext reference". Both the 4‑thread and 8‑thread results are valid ciphertexts within the noise bound, so their errors fall within tolerance.

This leads to a more general observation:

"Numerical closeness" and "identical result" are distinct properties, and the former cannot imply the latter.

In floating‑point we are accustomed to errors being continuous; however, in integer modular arithmetic with noise, differences can be discontinuous—two results may be identical or arbitrarily different, while their "errors" appear normal.

4. Why the Fix Is "Seeding by k"

The fix is straightforward: since randomness cannot be eliminated, make it a function of the input.

The approach is to seed by the automorphism index k. This path is already available because the codebase is organized by k:

c int ckks_gk_gen_k(ckks_gk_t *gk, const ckks_sk_t *sk, const ckks_ctx_t *ctx, uint64_t k); int ckks_rotate_k(ckks_ct_t ct, ..., uint64_t k); / general Galois σ_k (k any odd) */

In other words, the structure already indexes by k; only the random seeding had not caught up. The difficulty lies not in changing the architecture but in modifying the seeding points, and ensuring that every place that consumes randomness is covered (key generation, encryption, and any operation that samples noise).

Why this fixes the problem: once seeding depends only on k (and other deterministic inputs), "which random numbers thread 5 draws" is no longer determined by scheduling. Each logical object gets its own deterministic random stream, independent of who executes it or how many executors there are.

5. Current Status and Honest Statement

Source code status (as of writing):

c static _Thread_local uint64_t ckks_rng_state = 0x243F6A8885A308D3ull; /* fixed constant, inference path */

The only time‑related seeding in the file occurs in the self‑test function:

c int ckks_self_test(void) { ... ckks_rng_state = (uint64_t)time(NULL) ^ 0xDEADBEEFCAFEBABEull; }

It is not on the inference path and has no effect on actual lay/boot computation.

Therefore, the external statements are as follows:

All reproducibility claims must be tied to T23_NT.

6. A Second Case of the Same Class: Lazy Initialization Triggered Concurrently on First Access

In the bootstrap driver there is a fix record:

tab_prepare(n); /* M1c fix: coeff_to_slot/slot_to_coeff omp region concurrent first trigger ... */

Some precomputed tables were originally lazily initialized upon first access inside a parallel region. Multiple threads entering "for the first time" concurrently triggered initialization, and the result depended on which thread arrived first.

This is the same class of problem as the RNG seeding:

Common theme: execution order is treated as an implicit input.

7. A Reusable Checklist

If you work on any pipeline that combines parallelism, randomization, and result comparison, the following patterns are worth checking:

1. Thread‑local random state (_Thread_local / thread_local / TLS RNG), especially when the initial value is a constant;
2. Lazy initialization triggered by first access inside a parallel region;
3. Floating‑point reduction order: different grouping of parallel sums leads to different bit‑level results;
4. Nondeterministic partitioning strategies: dynamic scheduling (schedule(dynamic)), work stealing;
5. Hash/dictionary traversal order: in some languages, iteration order depends on insertion order or memory layout;
6. Time or addresses used in computation: using time(), pointer values as seeds or inputs.

The criterion is simple: ask "Does this result depend only on the input?" If the answer involves "depends on scheduling/timing/memory layout", it is not deterministic.

8. Safety Boundaries

The parameters described in this article are at the mechanism‑verification level, far below the 128‑bit security level required for HE parameters, and must not be used to protect real data.

This article addresses the localization and conclusion of a real reproducibility defect.

It does not address security strength or performance superiority (performance differences between 4 and 8 threads are out of scope).

Another necessary disclaimer: the RNG referenced in this article is a prototype‑level xorshift (the source comment itself says "prototype"). It was not designed for cryptographic security and should not be used as a secure random source.

9. Outstanding Issues

• The patch has not been applied yet. The solution is clear and the entry points exist, but doing is not the same as saying. Until it lands, any "bit‑level reproducibility" conclusion carries an asterisk.
• The scope of the fix needs auditing. It is not enough to fix seeding points; all paths that consume randomness must be verified—missing one means the problem can reappear with lower probability (harder to detect).
• No automatic regression check exists. Ideally, CI should include a test that compares bytes for the same input with different thread counts and alerts on mismatch. Currently, comparison is manual.
• Implicit inputs beyond T23_NT have not been systematically reviewed. For example, stage parameters like g_fold / g_chk, and the order in which precomputed tables are built, should be checked against the checklist in §7.

Sources:

• cnblogs.com project practice article: "【FHE】（十三）：位级可复现性——4 线程与 8 线程为什么算出不同的结果"
• NVIDIA cuBLAS documentation (docs.nvidia.com) on nondeterministic multi‑stream execution