Paper deep dive
Derandomizing Dense Binary Hypervector Codebooks for Quantized Scalars
Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov, Denis Kleyko, Vaclav Snasel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/1/2026, 8:23:05 AM
Summary
This paper presents a derandomization framework for generating dense binary hypervector codebooks for quantized scalars in Hyperdimensional Computing (HDC). It addresses finite-dimensional deviations from target similarity laws (exponential or linear decay) caused by sampling noise and random imbalances. The authors introduce variants that constrain initial Hamming weight, update counts, and update balance, deriving exact finite-dimensional expressions for bias, variance, and RMSE. Simulations validate that these constraints reduce specific sources of similarity mismatch, providing guidance for hardware-efficient HDC implementations.
Entities (10)
Relation Signals (7)
Derandomization Framework โ targets โ Dense Binary Hypervectors
confidence 95% ยท We develop a transition-based derandomization framework for dense binary scalar codebooks
Derandomization Framework โ supports โ Exponential Similarity Law
confidence 93% ยท The framework separates the target similarity law... across two target-similarity families, with similarity decaying exponentially
Derandomization Framework โ supports โ Linear Similarity Law
confidence 93% ยท The framework separates the target similarity law... across two target-similarity families, with similarity decaying ... linearly
Fixed-kpD โ constrains โ Hamming Weight
confidence 92% ยท Fixed-kpD additionally enforces equal-swap balance... preserve exactly D/2 ones at every level
Derandomization Framework โ reduces โ Bias
confidence 90% ยท show how each constraint removes or reduces a specific source of similarity mismatch... derive exact finite-dimensional expressions for bias
Derandomization Framework โ reduces โ Variance
confidence 90% ยท show how each constraint removes or reduces a specific source of similarity mismatch... derive exact finite-dimensional expressions for ... variance
Derandomization Framework โ reduces โ Root Mean Square Error
confidence 90% ยท show how each constraint removes or reduces a specific source of similarity mismatch... derive exact finite-dimensional expressions for ... root-mean-square error
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Hyperdimensional computing and vector symbolic architectures often represent quantized scalar levels by dense binary codebooks whose level-to-level similarity is intended to follow a prescribed function of scalar separation. At finite dimensionality, randomized scalar codebook constructions deviate from this target because of sampling noise, random-start imbalance, update-count fluctuations, component dependence, and finite-capacity effects. We develop a transition-based derandomization framework for dense binary scalar codebooks across two target-similarity families, with similarity decaying exponentially or linearly with level separation. The framework separates the target similarity law, the derandomization variant, and the concrete generator construction, making explicit how initialization, selection, update, and capacity-handling mechanisms shape the induced similarity profile. We formalize derandomization variants that separately constrain initial Hamming weight, update-count variability, and update balance, thereby controlling distinct sources of finite-dimensional error. For each family and variant, we derive the induced mean similarity, identify realization-wise and mean target-matching regimes, and derive exact finite-dimensional expressions for bias, variance, and root-mean-square error. Simulations across dimensions, quantization ranges, reference scalar levels, and generator constructions validate the theory and show how each constraint removes or reduces a specific source of similarity mismatch. The results provide practical guidance for choosing scalar codebook generators that more closely match a desired similarity law under finite-dimensional and hardware-relevant constraints.
Tags
Links
- Source: https://arxiv.org/abs/2609.38471v1
- Canonical: https://arxiv.org/abs/2609.38471v1
Trouble viewing inline? Open PDF directly โ
Full Text
166,862 characters extracted from source content.
Expand or collapse full text
1 Accepted, Neural Computation. Derandomizing Dense Binary Hypervector Codebooks for Quantized Scalars Dmitri Rachkovskij 1,2 , Evgeny Osipov 1 , Olexander Volkov 2 , Denis Kleyko 3,4 , Vaclav Snasel 5 1 Department of Computer Science, Electrical and Space Engineering, Luleรฅ University of Technology, 971 87 Luleรฅ, Sweden 2 Institute of Information Technologies and Systems, 03187 Kyiv, Ukraine 3 AI, Robotics and Cybersecurity Center (ARC) and Department of Computer Science, รrebro University, 70182 รrebro, Sweden 4 Intelligent Systems Lab, Research Institutes of Sweden, 16440 Kista, Sweden 5 Department of Computer Science, VSB - Technical University of Ostrava, 708 00 Ostrava- Poruba, Czech Republic Abstract Hyperdimensional computing and vector symbolic architectures often represent quantized scalar levels by dense binary codebooks whose level-to-level similarity is intended to follow a prescribed function of scalar separation. At finite dimensionality, randomized scalar codebook constructions deviate from this target because of sampling noise, random-start imbalance, update-count fluctuations, component dependence, and finite-capacity effects. We develop a transition-based derandomization framework for dense binary scalar codebooks across two target-similarity families, with similarity decaying exponentially or linearly with level separation. The framework separates the target similarity law, the derandomization variant, and the concrete generator construction, making explicit how initialization, selection, update, and capacity-handling mechanisms shape the induced similarity profile. We formalize derandomization variants that separately constrain initial Hamming weight, update-count variability, and update balance, thereby controlling distinct sources of finite-dimensional error. For each family and variant, we derive the induced mean similarity, identify realization-wise and mean target-matching regimes, and derive exact finite-dimensional expressions for bias, variance, and root-mean-square error. Simulations across dimensions, quantization ranges, reference scalar levels, and generator constructions validate the theory and show how each constraint removes or reduces a specific source of similarity mismatch. The results provide practical guidance for choosing scalar codebook generators that more closely match a desired similarity law under finite-dimensional and hardware-relevant constraints. Keywords: Hyperdimensional computing; Dense binary hypervectors; Scalar codebook generation; Derandomization; Similarity-preserving encodings 2 1 Introduction Hyperdimensional Computing / Vector Symbolic Architectures (HDC/VSA) (Kanerva, 2009), (Gayler, 2004), (Neubert et al., 2019), (Thomas et al., 2021), (Aygun et al., 2023), (Clarkson et al., 2023), (Thomas et al., 2023), (Stock et al., 2024), (Reimann, 2025) constitute a multi-faceted framework at the intersection of symbolic and neural-network based Artificial Intelligence. Beyond conventional machine learning (ML) such as classification (Kleyko et al., 2018), (Ge & Parhi, 2020), (Dewulf et al., 2025), HDC/VSA has been explored in resource- constrained scenarios, including embedded and edge computing. This interest is reinforced by the fact that HDC/VSA provides a computational paradigm for emerging hardware (Kleyko, Davies, et al., 2022). A central task in HDC/VSA is to transform data (scalars, vectors, sequences, graphs) into hypervectors (HVs) so that HV similarity reflects task-relevant relationships in the input space. These transformations are typically randomized and nonlinear. The required dimensionality and HV format depend on the application: complex structured representations, such as graphs, may require thousands of dimensions, whereas edge computing benefits from compact representations as well as energy- and compute-efficient formats such as binary HVs. This makes the behavior of HDC/VSA representations at practical finite dimensionalities an important design consideration. For numeric data, HDC/VSA commonly uses fixed randomized nonlinear transformations designed so that nearby inputs produce similar HVs while distant inputs produce dissimilar HVs. Prior work distinguishes three broad approaches for mapping numeric data to HVs: compositional, explicit receptive-field-based, and random-projection-based (Rachkovskij et al., 2013), (Kleyko, Rachkovskij, et al., 2022). In this paper, we focus on the scalar representations under the compositional approach (Rachkovskij & Fedoseyeva, 1990), (Kussul et al., 1991a, 1991b) as summarized in (Rachkovskij, Slipchenko, Kussul, et al., 2005; Rachkovskij, Slipchenko, Misuno, et al., 2005). In this approach, each component of a numeric input vector (a scalar) is first transformed into a similarity-preserving scalar HV. These scalar HVs can subsequently be bound to their respective feature identifiers and superimposed to encode numeric feature vectors or used as constituents of more general compositional representations (e.g., (Plate, 2000), (Rachkovskij, 2001), (Kahawala et al., 2026)), where preserving controlled similarity relations at the scalar level remains important. Here we isolate the scalar-codebook stage and study the accuracy and implementation properties of its generator constructions. The original scalar codebook constructions were developed for highly randomized distributed representations and specialized wide-word hardware, where noise tolerance and compositional capacity were central design considerations (Kussul et al., 1991a), (Kussul et al., 1991b), (Rachkovskij, Slipchenko, Kussul, et al., 2005). Accordingly, they did not enforce constant Hamming weight or fixed numbers of component updates between scalar levels. 3 Current HDC deployments increasingly use dense binary HVs (but see (Haputhanthri et al., 2026)) directly in similarity search and classification and emphasize predictable behavior and implementation efficiency. In this setting, uncontrolled initialization and update randomness can produce finite-dimensional (finite-D) deviations from the intended similarity law. Existing work has largely focused on proposing or applying scalar-codebook constructions rather than systematically characterizing these deviations and the mechanisms that produce them. This motivates a systematic treatment of dense binary scalar generators that progressively reduce randomness while targeting a prescribed similarity law, together with finite-D analysis of the resulting bias and variability. To address this gap, we study dense binary scalar codebooks with target one-density ํ = 1/2 under two prescribed similarity-law families, with exponential or linear dependence on level separation. We introduce a common set of derandomization variants that constrain initial Hamming weight (i.e., the number of 1-components), the number of component updates per transition, and the balance between 1โ0 and 0โ1 updates. For each family, we specify concrete generator constructions, derive their induced mean similarity and finite-D bias, variance, and root-mean-square error (RMSE), and validate the predictions by simulation. The present study is restricted to scalar codebooks; full vector encodings and task-level behavior are left to companion work. Our main contributions are as follows: 1. We develop a unified derandomization framework for dense binary scalar hypervector codebooks, covering exponential and linear target-similarity families and a common set of constraints on initialization, update count, and update balance. 2. We specify family- and variant-specific generator constructions and analyze how component selection, reuse, update, and capacity handling mechanisms shape the induced similarity behavior, including conditions for realization-wise or mean target matching. 3. We develop exact finite-D average-case theory for the induced similarities, deriving their means and variances and the resulting bias and root-mean-square error relative to the target similarity law. 4. We validate the theory empirically across similarity families, generator constructions, dimensionalities, quantization ranges, and reference scalar levels, and identify how the derandomization mechanisms affect similarity accuracy, providing mechanism-based guidance for generator and parameter selection. 2 Background and Related Work 2.1 HDC/VSA: Hypervector Formats and Similarity In HDC/VSA, data items are represented by HVs whose dimensionality (number of components) is typically in the hundreds to tens of thousands, depending on the application. The underlying VSA model determines the HV format: common choices include real-valued 4 representations such as Holographic Reduced Representations (Plate, 1995), complex-valued variants (Plate, 2003), bipolar โ1,+1 (Multiply-Add-Permute) (Gayler, 1998), dense binary (Binary Spatter Code) (Kanerva, 1994), (Kanerva, 1996), sparse binary (Sparse Binary Distributed Representations) (Rachkovskij, 2001), (Laiho et al., 2015). A standard design principle is that unrelated / dissimilar data items (such as symbols) are assigned independently generated HVs. Similarity is then controlled by construction for related items. Similarity measures depend on the format: dot-product or cosine similarity is common for real-valued HVs, while for binary HVs similarity is often evaluated via Hamming distance (the number of different components) or overlap-based dot-product similarity. Throughout this paper, we focus on dense binary HVs with target one-density ํ = 1/2. 2.2 Scalar Hypervectors in the Compositional Approach Under the compositional approach, each quantized scalar input is assigned an HV from a codebook constructed to enforce a desired similarity profile over scalar levels, such as exponential or linear decay with level separation. To represent a full numeric feature vector, scalar value HVs are bound to their corresponding feature identifiers, and the resulting HVs are aggregated by superposition. The scalar codebook contributes to the similarity structure inherited by the final vector-level HV, and thus influences performance and implementation requirements. This paper isolates the scalar stage and studies scalar codebook generators with progressively reduced randomness. We analyze how closely the resulting similarity profiles follow their intended targets at practical dimensionalities and quantization levels. 2.3 Previous and Related Work 2.3.1 Historical Context and Motivation The original scalar codebook constructions of (Rachkovskij, Slipchenko, Kussul, et al., 2005) were developed under assumptions that differ from many current HDC deployments. They targeted specialized โassociativeโprojective neurocomputersโ (Kussul et al., 1991a), (Kussul et al., 1991b) supporting efficient bit-wise operations on very wide machine words of 512 and 2048 bits, potentially extending to the full HV dimensionality, and tolerated unreliable bits in memory and even in registers. They were also motivated by brain-inspired, fully-distributed high-dimensional representations, where variability and noise are intrinsic, and strict constraints on Hamming weight (i.e., the number of 1-components) or update size are not naturally justified. Accordingly, the original constructions were highly randomized and did not enforce constant Hamming weight in either the HVs or their updates. These randomized high- dimensional hypervectors were intended primarily as constituents for constructing larger compositional structures, including nodes, edges, subgraphs, and graphs (Kahawala et al., 2026), without changing dimensionality. This motivated large initial dimensionalities both to support composition and to stabilize the statistical properties of randomized representations. The original work was developed in the setting of Sparse Binary Distributed Representations 5 (Rachkovskij & Kussul, 2001), where sparsity is a central design feature, although the underlying ideas extend to other HDC formats. Subsequent work has adapted this compositional approach to different HV formats and basic operations used to construct compositional representations, with increasing emphasis on direct use of HVs in classification or similarity search rather than primarily as constituents of larger structured representations. This shifted the design priorities from neurobiological plausibility and highly randomized, noise-tolerant representations, toward more deterministic, hardware-friendly constructions with predictable behavior in similarity search and classification and efficient implementations in resource-constrained systems. These changes make several open issues practically important. Dense binary HVs can support reduced dimensionalities and simpler hardware datapaths, while uncontrolled randomness and Hamming-weight drift can translate into variability of the similarity structure and consequently of task performance. Existing work has largely focused on proposing and deploying scalar constructions, rather than systematically analyzing their finite-D behavior. This motivates scalar generators that reduce or remove selected sources of randomness while targeting a prescribed similarity law, together with finite-D accuracy analysis of realized similarities under practical dimensionalities and run budgets. Early schemes for similarity-preserving scalar HVs were proposed independently by (Rachkovskij & Fedoseyeva, 1990) and (Smith & Stanford, 1990). These and related constructions (Rachkovskij, Slipchenko, Kussul, et al., 2005), (Purdy, 2016) can be interpreted as implementing a โcomponent flowโ from the HV of one quantization level to the next. From this perspective, whether components are selected for update with or without replacement determines the resulting similarity-law family. 2.3.2 Exponential Target Similarity Law Scatter codes (Smith & Stanford, 1990) and the SubtractโAdd scheme in (Rachkovskij, Slipchenko, Kussul, et al., 2005), also used in (Rachkovskij & Fedoseyeva, 1990), generate correlated scalar HVs by iteratively updating a random reference HV. At each level, selected components are flipped and remain eligible for selection at subsequent levels. This with- replacement mechanism yields an expected similarity that decreases geometrically with level separation, producing an exponential target similarity law. Applications to classification were discussed, for example, in (Rachkovskij & Fedoseyeva, 1990) and (Kleyko et al., 2018). 2.3.3 Linear Target Similarity Law Here, linear refers to dependence on the nonnegative level separation; for a fixed reference level, the similarity profile over comparison levels is triangular (piecewise linear). The concatenation construction of (Rachkovskij, Slipchenko, Kussul, et al., 2005) assigns independent random reference HVs to the minimum and maximum levels. At level ํ, the first (ํโํ)ํท/ํ components are taken from the first reference HV and the last ํํท/ํ components from the second, producing a linear similarity profile between the two references. Related constructions obtain linear similarity by progressively flipping components of a single 6 reference HV without replacement (Widdows & Cohen, 2015), (Rahimi et al., 2016), (Kleyko et al., 2018). This can be viewed as a two-reference construction where the second reference is the complement of the first, yielding a linear decay to zero similarity at the maximum level. Many implementations flip a fixed number of previously unused components per level: ํท/(2ํ) as in (Rahimi et al., 2016), (Smets et al., 2023) yields a linear slope toward the similarity between the initial and final references. While flipping ํท/ํ components, as in (Hsiao et al., 2021), (Huang et al., 2021), (Smets, Rachkovskij, Osipov, Volkov, et al., 2025), (Smets, Rachkovskij, Osipov, Van Leekwijck, et al., 2025) reaches zero similarity at ํ = ํ. Related interpolation schemes were proposed in (Cohen et al., 2013), (Widdows & Cohen, 2015), (Kleyko et al., 2018). Piecewise-linear concave similarity profiles can be formed by combining multiple reference HVs with different slopes. 2.3.4 Deterministic Localist Encodings with Linear Similarity Deterministic or partially distributed binary encodings provide low-randomness counterparts to distributed constructions. In โfloatโ (closeness, bar, pointer, sliding) codes (Penz, 1987), level ํ is represented by ํ consecutive active units starting at position ํ, requiring ํ+ํ units in total. The dot-product similarity decreases linearly from ํ to 0 between the codes of ํ and ํ+ํ for ํ โ [0,ํ], and is zero for larger separations. For ํ = ํ, each code has half of the units active, and each level transition swaps one active and one inactive component, preserving constant Hamming weight. Multifloat codes (Kussul et al., 1993) combine floats of different lengths to obtain piecewise-linear concave similarity profiles. In thermometer (unary) codes (Penz, 1987), (Jackel et al., 1987), ํ of ํ units are active, so each level transition activates one additional component. The stack code of (Healy & Caudell, 1997) appends the complement (0โ1) of the thermometer code, doubling dimensionality and yielding a float code with ํ = ํ. Recent work on compositional pipelines includes float encoding followed by multiplicative binding with feature-ID HVs: (Vergรฉs et al., 2023) termed it โflocetโ following a typo in (Rachkovskij, Slipchenko, Kussul, et al., 2005). Unary or thermometric encodings in compositional pipelines have also been considered in (Kleyko et al., 2021), (Roodsari et al., 2024), (Moghadam et al., 2024), (Masum et al., 2025), (Moghadam et al., 2025). 3 Methodology and Derandomization Framework We propose and study a unified derandomization framework for constructing dense binary HV codebooks for quantized scalar levels. The framework distinguishes the prescribed target similarity law, the derandomization variant that specifies which sources of finite-D variability are constrained, and the generator construction that implements those constraints. Section 3.1 develops the common derandomization hierarchy used for both exponential and linear similarity families; section 3.2 defines the notation, similarity measures, and target laws; and section 3.3 defines the error metrics and evaluation protocol used in our analysis. 7 3.1 Framework and Derandomization Hierarchy For scalar representations, we begin with highly randomized generator constructions similar in spirit to the SubtractโAdd scheme of (Rachkovskij, Slipchenko, Kussul, et al., 2005), in which both the initial hypervector and the components updated at each level transition are sampled probabilistically. Consequently, in the Baseline constructions, both |ํฑ เฏค | and the number of components updated in a level transition vary across realizations and, generally, across levels within a realization. The derandomization hierarchy introduced below progressively constrains selected sources of this variability. ํ, Let ํฑ เฏค เฏคเญเฌด เฏ , with ํฑ เฏค โ0,1 เฎฝ , denote the hypervector codebook, and consider the level transition from ํฑ เฏค to ํฑ เฏคเฌพเฌต . For the constructions studied here, the principal distinction between the two target-similarity families is whether components may be reused across level transitions. In the exponential family, components remain eligible for selection in later transitions; selection is therefore with replacement across levels. In the linear family, a component selected in one transition is not selected again; so selection is without replacement across levels. In the constructions analyzed later, these two across-level selection rules lead, respectively, to exponential and linear dependence of expected similarity on level separation. Throughout this paper, we consider dense binary hypervectors with target one-density ํ = 1/2, so the target |ํฑ เฏค |=ํํท=ํท/2 at every level. Depending on the derandomization variant, this target is satisfied either in expectation or in every realization. Within either target family, derandomization progressively controls three sources of variability: (1) the initial value |ํฑ เฌด |; (2) the total number of components updated in each level transition; (3) the balance between 1โ0 and 0โ1 updates within a transition. Fixing |ํฑ เฌด | removes random-start imbalance in the starting hypervector. Fixing the total update count removes update-count variability. Enforcing equal numbers of 1โ0 and 0โ1 updates prevents Hamming-weight drift and preserves |ํฑ เฏค | at every level. We call an update balanced in expectation when the expected numbers of 1โ0 and 0โ1 changes are equal. Such updates preserve ํ[|ํฑ เฏค |], although |ํฑ เฏค | may vary across levels and realizations. Equal-swap updates enforce this balance in every transition. In the linear family, the Fixed-kpD constructions preserve exactly ํท/2 ones at every level and match the linear target law realization-wise. The deterministic linear constructions introduced in section 5 are instances of this variant. Figure 1 summarizes the derandomization hierarchy considered within both target- similarity families, and Table 1 states the corresponding constraints. The choice between exponential and linear target laws is separate from this hierarchy and determines the across- level component-reuse rule. Each target family realizes these variants through its own generator constructions. 8 A derandomization variant does not uniquely determine a generator construction. Different constructions may satisfy the same variant constraints while differing in their concrete component-selection and update mechanisms. Such differences may preserve the same induced mean-similarity law while affecting finite-D bias and variance. Figure 1: Scalar codebook derandomization hierarchy. The target family determines the across- level component-reuse rule: exponential-family constructions use with-replacement reuse, whereas linear-family constructions use without-replacement reuse. Both target families are organized by the same derandomization hierarchy, but each family realizes the variants through its own generator constructions. Baseline (Bernoulli) branches into the single-constraint variants Fixed-pD and Fixed-F; Fixed-FpD combines these constraints; Fixed-kpD additionally enforces equal-swap balance. Each variant may admit one or more family-specific generator constructions. Table 1: Constraints defining the derandomization variants at ํ = 1/2. โBalanced in expectationโ means E[ํ เฌตเฌด ] = E[ํ เฌดเฌต ] for the constructions studied in sections 4 and 5. The quantities D/2, F, and k are assumed to be integers whenever required. Variant |ํฑ เฌด | Updates per transition Number of 1โ0/0โ1 flips |ํฑ เฏค |,ํ>0 Baseline Random; E[|ํฑ เฌด |] = ํท/2 Random Random; balanced in expectation Not fixed; E[|ํฑ เฏค |] = ํท/2 Fixed-pD ํท/2 exactly Random Random; balanced in expectation Not fixed; E[|ํฑ เฏค |] = ํท/2 Fixed-F Random; E[|ํฑ เฌด |] = ํท/2 ํน exactly Random; balanced in expectation Not fixed; E[|ํฑ เฏค |] = ํท/2 Fixed-FpD ํท/2 exactly ํน exactly Random; balanced in expectation Not fixed; E[|ํฑ เฏค |] = ํท/2 Fixed-kpD ํท/2 exactly 2ํ exactly ํ in each direction ํท/2 exactly 3.2 Notation, Similarity Measures, and Target Laws Table 2 summarizes the notation used throughout the theoretical and empirical analysis. Table 2: Main notation. Symbol Meaning 9 ํท hypervector dimensionality (number of components) ํ target one-density (throughout this paper ํ = 1/2) ํ quantization-level index ํ maximum quantization-level index ํ, ํ generic level indices ํฑ เฌด initial hypervector ํฑ เฏค hypervector assigned to level ํ ฮ := |ํโํ| level separation w.o.r. without replacement w.r. with replacement ํ nominal per-component flip rate in one level transition ฯ one-step correlation coefficient (decay parameter) for the exponential family ํน fixed total number of component flips in one level transition ํ เฌตเฌด number of 1โ0 flips in one level transition ํ เฌดเฌต number of 0โ1 flips in one level transition ํ(ํ,ํ) Overlap between ํฑ เฏ and ํฑ เฏ ํ(ํ,ํ) Normalized overlap similarity sim ham (ํ,ํ) Normalized Hamming similarity |ํฑ เฏค | changes according to |ํฑ เฏค+เฌต | = |ํฑ เฏค | โํ เฌตเฌด +ํ เฌดเฌต . Consequently, E[ํ เฌตเฌด ] = E[ํ เฌดเฌต ] preserves E[|ํฑ เฏค |], whereas ํ เฌตเฌด = ํ เฌดเฌต preserves the realized |ํฑ เฏค | in every transition. If E[|ํฑ เฌด |] = ํท/2, balance in expectation gives E[|ํฑ เฏค |] = ํท/2 for all ํ. If |ํฑ เฌด | = ํท/2 and every transition is exactly balanced, then |ํฑ เฏค | = ํท/2 for every level and every realization. Constant Hamming weight is therefore a property of the complete generator construction, including both its initialization and its update rule, and is stronger than balance in expectation. For binary HVs u and v, define their overlap and Hamming distance by sim เญขเญญเญฒ (u,v) := โ (ํข เฏ โง ํฃ เฏ ) ํ and dist เญเญเญซ (u,v) := โ (ํข เฏ โ ํฃ เฏ ) ํ , where โง and โ denote component-wise AND and XOR, respectively. For codebook levels ํ and ํ, let ํ(ํ,ํ) = sim dot (ํฑ เฏ ,ํฑ เฏ ). The normalized overlap similarity is ํ(ํ,ํ) = ํ(ํ,ํ)/(ํํท). At ํ = 1/2, this reduces to ํ(ํ,ํ) = 2 ํ(ํ,ํ)/ํท. We also use the normalized Hamming similarity sim ham (ํ,ํ) = 1โ dist Ham (ํฑ เฏ ,ํฑ เฏ )/ํท. The Hamming weight is |ํฎ|= โ ํข เฏํ , the number of components equal to 1, and its one-density is |ํฎ|/ํท. For example, let ํท = 8, ํ = 1/2, and ํฑ เฏ =(1,1,1,1,0,0,0,0), ํฑ เฏ =(1,1,0,1,1,0,0,0). Both vectors have Hamming weight four, and one-density 1/2. They overlap in three 1- components and differ in two components, so ํ(ํ,ํ)=3, dist Ham (ํฑ เฏ ,ํฑ เฏ )=2. Therefore, ํ(ํ,ํ)=3/4, sim ham (ํ,ํ) = 1โ2/8=3/4. For a given generator construction, ํ(ํ,ํ) denotes the intended normalized similarity between levels ํ, ํ. We call ํ the target similarity law. Both target laws considered in this 10 paper are shift-invariant: they depend on the level indices only through their separation, ํ(ํ,ํ) = ํ(ฮ), ฮ := |ํโํ|. The exponential target law is ํ exp (ํ,ํ) = ํ exp (ฮ) = 1/2+(1/2) ฯ ฮ , (3.1) where ฯ is the prescribed one-step decay parameter of the target law. Section 4 specifies how the update parameter ํ of each exponential-family generator is chosen to reproduce this decay in the induced mean similarity. The linear target law is ํ lin (ํ,ํ) = ํ lin (ฮ) = max(0,1โ ฮยทํน/ํท) = max(0,1โฮ/ํ). Here, linear refers to the dependence on the nonnegative level separation ฮ = |ํโํ|; as a function of the signed difference ํโํ, this law is triangular and piecewise linear. Section 5 specifies how the linear-family generators realize this law using ํน = ํท/ํ, equivalently ํ=ํน/ํท = 1/ํ, including the finite-capacity corrections of the random-count constructions. For a realized codebook, ํ(ํ,ํ) is generally a random quantity. Its generator-induced mean similarity is E[ํ(ํ,ํ)], which we compare with the intended target law ํ(ํ,ํ). For a fixed anchor level ํ, varying ํ over 0,...,Q gives a similarity profile for ํ(ํ,ํ), ํ(ํ,ํ), or E[ํ(ํ,ํ)]. Although the target laws are anchor-independent, realized similarities and some construction-specific induced mean profiles may exhibit anchor dependence. 3.3 Error Metrics and Evaluation Protocol This section defines the error quantities and their finite-ํ empirical estimates used to compare the generator constructions with the target similarity law. Unless stated otherwise, E[.] and Var(.) denote expectation and variance over independent generator realizations. Empirical quantities carry the subscript emp and are computed from ํ independent realizations. 3.3.1 Point-wise Quantities and Finite-ํ Empirical Estimates For fixed levels ํ,ํ, the realized similarity ํ(ํ,ํ) is a random variable. Its mean and variance over generator realizations are ฮผ(ํ,ํ) := E[ํ(ํ,ํ)], v(ํ,ํ) := Var(ํ(ํ,ํ)). The corresponding point-wise bias and mean-squared error relative to the target similarity law are bias(ํ,ํ) := ฮผ(ํ,ํ)โํ(ํ,ํ), MSE(ํ,ํ) := E[(ํ(ํ,ํ)โํ(ํ,ํ)) เฌถ ]. For ํ independent realizations, let ํ เฏก (ํ,ํ) denote the similarity in realization ํ. Define ฮผ emp (ํ,ํ) := (1/ํ)ยทโ เฏก = เฌต เฏ ํ เฏก (ํ,ํ), v emp (ํ,ํ) := (1/ํ)ยทโ เฏก = เฌต เฏ (ํ เฏก (ํ,ํ)โฮผ emp (ํ,ํ)) เฌถ , bias emp (ํ,ํ) := ฮผ emp (ํ,ํ)โํ(ํ,ํ), MSE emp (ํ,ํ) := (1/ํ)ยทโ เฏก = เฌต เฏ (ํ เฏก (ํ,ํ)โํ(ํ,ํ)) เฌถ . With the 1/ํ normalization used for v emp (ํ,ํ), they satisfy the exact finite-sample identity MSE emp (ํ,ํ) = v emp ( ํ,ํ ) + bias emp เฌถ ( ํ,ํ ) . 3.3.2 Reference-Level Averaging and RMSE, Bias, and Variance Summaries For a fixed anchor level ํ, define averaging over all comparison levels ํ by mean เฏ [ํ(ํ,ํ)] := (1/(ํ+1)) โ เฏ = เฌด เฏ ํ(ํ,ํ). We report the corresponding root-mean-square (RMS) summaries over ํ; BiasRMS(ํ), VarRMS(ํ), and RMSE(ํ) denote the nonnegative square roots of the 11 corresponding squared definitions: BiasRMS เฌถ (ํ) := mean เฏ [bias เฌถ (ํ,ํ)], VarRMS เฌถ (ํ) := mean เฏ [v(ํ,ํ)], RMSE เฌถ (ํ) := mean เฏ [E[(ํ(ํ,ํ)โํ(ํ,ํ)) เฌถ ]]. Their empirical counterparts are BiasRMS emp เฌถ (ํ) := mean เฏ [bias emp เฌถ (ํ,ํ)], VarRMS emp เฌถ (ํ) := mean เฏ [v emp (ํ,ํ)], RMSE emp เฌถ (ํ) := mean เฏ [MSE emp (ํ,ํ)]. For each fixed (ํ,ํ), the biasโvariance decomposition gives ํํํธ(ํ,ํ) = v(ํ,ํ)+bias เฌถ (ํ,ํ). Averaging over ํ yields RMSE เฌถ (ํ) = VarRMS เฌถ (ํ)+BiasRMS เฌถ (ํ). The empirical definitions satisfy the corresponding exact identity RMSE emp เฌถ (ํ) = VarRMS emp เฌถ (ํ)+BiasRMS emp เฌถ (ํ). 3.3.3 Finite-ํ Interpretation and Comparison with Theory The quantities ฮผ(ํ,ํ), v(ํ,ํ), bias(ํ,ํ), ํํํธ(ํ,ํ) are defined over generator realizations and therefore do not depend on the number N of Monte Carlo realizations. Their empirical counterparts are computed from N independent realizations. The empirical mean and MSE are unbiased for their population counterparts, whereas the squared empirical bias and the empirical variance have finite-ํ corrections because v emp is normalized by 1/ํ; the corresponding expectation identities are given in supplementary note 3.1. Section 6 provides the corresponding theoretical values bias th (ํ,ํ) and v th (ํ,ํ) for the generator constructions. Their anchor-wise summaries are computed using the same ํ- averaging definitions as in section 3.3.2: BiasRMS th เฌถ (ํ) := mean เฏ [bias th เฌถ (ํ,ํ)], VarRMS th เฌถ (ํ) := mean เฏ [v th (ํ,ํ)], and RMSE th เฌถ (ํ) := mean เฏ [v th (ํ,ํ)+bias th เฌถ (ํ,ํ)]. Section 7 reports the corresponding empirical summaries, with the primary comparison between RMSE emp (ํ) and RMSE th (a) at the same anchor level. 4 Exponential-Similarity Scalar Codebook Generation This section develops scalar codebook generators for the exponential family. Their defining structural principle is with-replacement component reuse across level transitions: components updated at earlier transitions remain eligible for selection at later transitions. We consider two update schemes, SubtractโAdd (SA) and SingleโCommit XOR (SC). For each scheme, we state the update rule, the density-preserving parameterization, the resulting one- step decay factor, and the vectorized implementation cost. Supplementary note 1 provides full derivations and properties of the SA and SC mean-similarity laws (1.1 and 1.2); comparison of the two schemes (1.3); and the complementary Markov-chain and eigenvalue interpretation (1.4). SA is included to connect the framework with classical scalar-codebook generators and to compare its exponential decay and implementation cost with SC. The derandomization variants and their finite-D analysis are developed for the SC scheme in sections 4.3 and 6.1. 4.1 Common Exponential Template The exponential family uses with-replacement reuse across levels: every component remains eligible for selection at each transition ํ โ ํ+1 , irrespective of earlier selections. The 12 update rule is level-homogeneous and permutation-invariant over component indices. Conditional on ํฑ เฏค , every component therefore has the same marginal transition rule. Fixed- count variants may introduce dependence among component selections within a transition; the mean-similarity analysis requires exchangeability rather than within-step independence. Initialization and Hamming weight control: We initialize ํฑ เฌด either with i.i.d. Bernoulli(1/2) components (so E(|ํฑ เฌด |) = ํท/2) or with a constant-weight vector ํฑ เฌด with |ํฑ เฌด | = ํท/2 exactly, chosen uniformly among all subsets of that size. Balanced-in-expectation updates preserve E[|ํฑ เฏค |] = ํท/2, whereas equal-swap constructions enforce |ํฑ เฏค | = ํท/2 at every level ํ in every realization by design. Under these conditions, the induced mean similarity depends on (ํ,ํ) only through ฮ := |ํโํ|, and follows the exponential law in Eq. (3.1), governed by a one-step decay factor ฯ (also known as retention, persistence, correlation coefficient, lag-1 autocorrelation coefficient) that controls how rapidly similarity decays with level separation. Sections 4.2 and 4.3 specify ฯ and the vectorized implementations for SA and SC. The Markov-chain interpretation is given in supplementary note 1.4. 4.2 SubtractโAdd and SingleโCommit Update Schemes The SA scheme applies two substeps at each transition ํโํ+1. Degrade changes each component currently equal to 1 to 0 with probability ํ โ [0,1], while leaving components equal to 0 unchanged. Refill then changes each post-Degrade 0 to 1 with probability ฮฑ := ํ/(1+ํ), while leaving components equal to 1 unchanged. At marginal one-density 1/2, (1โํ)/2+ฮฑ (1+ํ) /2 = 1/2, so the complete transition preserves the marginal one-density. The induced mean similarity is E[ํ(ํ,ํ)] = ํ เฏเฎบ (ฮ) = 1/2+(1/2)ฯ เฏเฎบ ฮ , with ฯ เฏเฎบ = (1โํ)/(1+ํ). The derivation and additional properties are given in supplementary note 1.1. In vectorized form, ํฒ = ํฑ เฏค โง ํ deg , ํฑ เฏค+เฌต = ํฒ โจ ํ ref , where ํ deg has Bernoulli(1โํ) and ํ ref has Bernoulli(ฮฑ) i.i.d. components. Both masks are sampled over all component indices; a sampled mask value changes a component only when its current state is eligible for the corresponding substep. The operation count per machine word is two Bernoulli-mask generations, one AND, and one OR. The SC scheme applies one update at each transition ํโํ+1. A mask ํ เฏค with i.i.d. Bernoulli(ํ) components is generated, and ํฑ เฏค+เฌต = ํฑ เฏค โ ํ เฏค . Thus, each component flips independently with probability ํ and at most once during a transition. At marginal one-density 1/2, the 1โ0 and 0โ1 probabilities are equal, so the marginal one-density is preserved. The induced mean similarity is E[ํ(ํ,ํ)] = ํ เฏเฎผ (ฮ) = 1/2+(1/2)ฯ เฏเฎผ ฮ , with ฯ เฏเฎผ = 1โ2ํ. The derivation and additional properties are given in supplementary note 1.2. Because each component can flip only once per transition, executed and net flips coincide. The operation count per machine word is one Bernoulli-mask generation and one XOR. 4.3 SingleโCommit Derandomization Variants and Generator Constructions 13 Section 3.1 defines the common derandomization variants. Here, we instantiate them for SC updates within the exponential family. At every level transition, the selected update set is committed once by XOR. The variants differ in their initialization, component-selection mechanism, and constraints on the update set. All SC XOR variants have the exponential mean- similarity form E[ํ(ํ,ํ)] = ํ เฏเฎผ (ฮ) = 1/2+(1/2)ฯ เฏเฎผ ฮ , with ฯ เฏเฎผ = 1โ2ํ, where ํ is the marginal per-component flip probability (ํ = ํน/ํท for fixed-count updates and ํ = 2ํ/ํท for equal-swap). For Baseline SC, this mean similarity profile follows from section 4.2; the corresponding finite-D results for all variants are developed in section 6.1. For Baseline SC, ํฑ เฌด has i.i.d. Bernoulli(1/2) components and each transition uses a fresh i.i.d. Bernoulli(ํ) mask. Fixed-pD changes only the initialization, sampling ํฑ เฌด uniformly subject to |ํฑ เฌด | = ํท/2. Fixed-F instead retains Bernoulli initialization but selects exactly ํน = ํํท components uniformly at each transition. Fixed-FpD combines |ํฑ เฌด | = ํท/2 with this fixed- count update. In all four variants, the 1โ0/0โ1 split is not fixed to be equal. A representative generator construction is illustrated in Figure 2. Fixed-kpD additionally enforces exact balance: starting from |ํฑ เฌด | = ํท/2, each transition selects k current 1-components and k current 0-components uniformly, with ํน =2k=ํํท and flips their union in one XOR commit. Hence |ํฑ เฏค | = ํท/2 for every q, with zero variance in the total flip count and the 1โ0/0โ1 split. Figure 2. Exponential-family SingleโCommit Fixed-FpD generator construction. The example uses ํท =16, |ํฑ เฌด | = ํท/2=8, and two successive updates with |ํ เฌด | = |ํ เฌต |=ํน =4. Blue mask components are selected for flip; orange HV components change by XOR. The red outline marks the component selected in both masks, illustrating with-replacement reuse. 5 Linear-Similarity Scalar Codebook Generation This section develops scalar-codebook generators for the linear family, whose defining structural principle is without-replacement component use across level transitions. Section 5.1 introduces this principle, the remaining-pool and deterministic equal-swap realizations, and the parameterization that yields linear decay over the full quantization range. Section 5.2 gives the corresponding mean-similarity analysis, including a general remaining-pool identity, random- count finite-capacity effects, and exactness conditions for fixed-count and equal-swap updates. Section 5.3 instantiates the five derandomization variants through their linear-family generator 14 constructions. Proofs and detailed finite-capacity derivations are provided in supplementary note 2, while finite-D bias, variance, and RMSE are analyzed in section 6.2 and supplementary note 3.3. 5.1 Basic Idea We construct scalar codebook generators that produce ํฑ เฏค เฏคเญเฌด เฏ โ0,1 เฎฝ with linear target law ํ lin (ฮ) := max(0,1โฮ/ํ). The key structural change in the linear family is without- replacement reuse across level transitions: each component can be flipped in at most one transition ํ โ ํ+1, ํ=0,...,ํโ1. The linear constructions preserve the SC update type used by their exponential SC counterparts, but change component reuse across levels: w.o.r. in the linear family, in contrast to w.r. reuse in the exponential family. This converts exponential decay into linear dependence on ฮ. How the linear target is attained depends on the construction: random-count constructions can have finite-capacity deviations near exhaustion, fixed-count constructions match it in mean overlap similarity and realization-wise normalized Hamming similarity, and Fixed-kpD matches it realization-wise for both similarities. We instantiate this in two ways. The remaining-pool w.o.r. construction maintains a shrinking set ํ เฏค of components not yet flipped by level ํ (relative to the initial level ํฑ เฌด ). Each step flips a subset of ํ เฏค , and flipped components leave the pool (w.o.r. across levels). The resulting mean similarity is linear except for terminal deviations from truncation of a stochastic selection rule near pool exhaustion. Lemma 5.1 formalizes this. In deterministic equal-swap constructions, the updated components are fixed by design rather than sampled independently for each realization; this yields the linear similarity profile. We consider the five derandomization variants from section 3, specialized to the linear family via w.o.r., and the corresponding generator constructions with their update / selection / truncation mechanisms. Throughout the linear-family constructions, ํน denotes the nominal number of newly flipped components per level transition, with corresponding flip-rate parameter ํ = ํน/ํท. We use ํน = ํท/ํ, equivalently ํ = 1/ํ. For fixed-count without-replacement constructions, this choice uses all ํท components exactly once over the ํ level transitions and exhausts the remaining pool at ํ = ํ, yielding the linear similarity law ํ lin (ฮ) = 1โฮ/ํ. For random- count constructions, ํน = ํท/ํ is the nominal transition count; truncation near exhaustion can produce the finite-capacity corrections. Other values of ํน are not considered in this paper. If ํน > ํท/ํ, fixed-count without- replacement updates exhaust the available components before ํ = ํ, thereby shortening the usable quantization range. If ํน < ํท/ํ, some components remain unflipped and therefore common even at the maximal separation ฮ = ํ, underusing the available representation capacity (Smets, Rachkovskij, Osipov, Volkov, et al., 2025). The corresponding relation between transition size, capacity, and terminal similarity differs for ํ < 1/2, (Rachkovskij, Slipchenko, Kussul, et al., 2005), but that regime is outside the scope of this paper. 15 The linear constructions are related to existing work on Hyperdimensional Computing representations (Thomas et al., 2023), (Kleyko, Rachkovskij, et al., 2022), (Kleyko et al., 2023), on sequence-similarity encoders (Rachkovskij, 2024), (Rachkovskij & Kleyko, 2022), and on structured codes for HDC (Raviv, 2024). We do not rely on their specific constructions, but they provide broader context for the role of similarity profiles and structured HVs in HDC. 5.2 Analysis In this section we state mean-similarity results for w.o.r. linear generators under assumptions on (i) how previously unused components are selected across levels and (i) how selection is truncated when the remaining pool is near exhaustion. The statements are phrased entirely in terms of the remaining-pool process. Section 5.3 maps the generator constructions to these assumptions. We first state Lemma 5.1, which expresses expected similarity E[ํ(ํ,ํ)] in terms of expected remaining-pool depletion. This lemma applies to any w.o.r. remaining-pool generator construction that flips only previously unused components, independently of the concrete selection mechanism, including fixed-order constructions that deterministically traverse a fixed ordering induced by an initial random permutation. The equal-swap constructions are treated separately because they yield the deterministic linear law. In that variant, each level transition additionally enforces ํ เฌตเฌด = ํ เฌดเฌต = ํ = ํท/(2ํ), and therefore |ํฑ เฏค | = ํท/2 exactly for all ํ. 5.2.1 Lemma 5.1 (W.o.r. Identity for Expected Similarity) Consider producing ํฑ เฏค เฏคเญเฌด เฏ โ0,1 เฎฝ by per-level XOR updates driven by a per-level flip mask (a binary pattern indicating which components are flipped in the transition ํ โ ํ+1) under w.o.r. dynamics: each component is flipped in at most one transition ํ โ ํ+1, ํ= 0,...,ํโ1. Let ํ เฏค โ 1,...,ํท denote the remaining pool after forming level ํ , i.e. the set of ํฑ เฌด component indices not yet flipped in transitions up to level ํ. Thus ํ เฌด = 1,...,ํท and ํ เฏค+เฌต โ ํ เฏค . Under w.o.r., each ํ เฏค is determined by the supports of the flip masks used up to level ํ (i.e., by which components have been flipped up to that level). Assume the following two conditions: (A) Complement-invariant initialization: ํฑ เฌด and its component-wise complement 1โํฑ เฌด have the same distribution. (Examples: ํฑ เฌด i.i.d. Bernoulli(1/2); if ํท is even, ํฑ เฌด uniform over all vectors in 0,1 เฎฝ with exactly ํท/2 ones). (B) Value-independent selection: For each transition ํ โ ํ+1, conditional on the current remaining pool ํ เฏค , the distribution of the flip mask used to form ํฑ เฏค+เฌต from ํฑ เฏค does not depend on the component values of ํฑ เฏค . Let ํฝ ~ Unif(1,...,ํท), independently of the generator randomness. All probabilities and expectations below are over the joint randomness of ํฝ, ํฑ เฌด , and the generator. Without loss of generality assume ํ โฅ ํ (if ํ < ํ, swap ํ and ํ). Then: (i) Pr(ํฅ เฏ (ํฝ) = ํฅ เฏ (ํฝ)) = 1โ(E[|ํ เฏ |]โE[|ํ เฏ |])/ํท, (i) E[ํ(ํ,ํ)] = Pr(ํฅ เฏ (ํฝ) = ํฅ เฏ (ํฝ)). 16 5.2.2 Random-Count Finite-Capacity Effects Two random-count mechanisms are used in section 5.3. In Pool-Bernoulli, the expected executed flip count equals F =D/Q while |ํ เฏค | โฅ F , whereas all remaining components are selected once |ํ เฏค |<F. Its mean similarity therefore follows ํ lin closely away from pool exhaustion, with finite-capacity corrections becoming appreciable near the terminal levels; see Proposition 1 in supplementary note 2.2.1. Random-count Perm-Scan traverses a fixed component ordering using random proposed update count ํ เฏคเฌพเฌต . For transition ํ โ ํ+1, it generates ํ เฏคเฌพเฌต ~ Binomial(ํท,1/ํ), but executes at most the number of components remaining in the unused pool. Because overshoots are truncated whereas undershoots leave components unflipped, the induced mean overlap similarity lies slightly above the linear target near pool exhaustion; Proposition 2 in supplementary note 2.2.2 gives the exact mean law. At the terminal pair (0,ํ), whose separation is โ =ํ, and for which ํ lin (ํ)=0, the residual mean overlap is, for large ํท, E[ํ(0,ํ)] โ ((1โ1/ํ)/(2ฯD)) เฌต/เฌถ , see Remark 3 in supplementary note 2.2.3. Empirically, the fixed-order variants show a slightly larger terminal bias than Pool-Bernoulli. 5.2.3 Fixed-Count and Equal-Swap Exactness Suppose that every transition flips exactly ํน = ํท/ํ previously unused components, where ํน is an integer. Then the remaining pool is depleted deterministically and, for ํ+ฮ โค ํ, E[ํ(ํ,ํ+ฮ)] = 1โฮโF/ํท = ํ lin (ฮ), while dist Ham (ํฑ เฏ ,ํฑ เฏ+ฮ ) = ฮโF. Thus, fixed-count constructions attain the target mean overlap similarity and the exact normalized Hamming similarity; see Corollary 4 in supplementary note 2.2.4. They do not necessarily preserve |ํฑ เฏค |, because the split between 1โ0 and 0โ1 flips remains random. The Fixed-kpD constructions in section 5.3 additionally enforce ํ = ํท/(2ํ) flips in each direction per transition. Consequently, |ํฑ เฏค | = ํท/2, ํ(ํ,ํ) = ํท/2โฮโํ, and ํ(ํ,ํ) = 1โฮ/ํ = ํ lin (ฮ) for all levels exactly, in every realization. 5.3 Linear-Similarity Derandomization Variants and Generator Constructions The linear-family generators instantiate the five derandomization variants using the remaining- pool and deterministic mechanisms analyzed above. Baseline uses i.i.d. Bernoulli(1/2) initialization and one of two random-count constructions: Pool-Bernoulli or random-count Perm-Scan. Fixed-pD uses the same constructions but initializes ํฑ เฌด uniformly subject to |ํฑ เฌด | = ํท/2. Their finite-capacity corrections are in section 5.2.2. Fixed-F uses Bernoulli initialization and flips exactly ํน=ํท/ํ previously unused components per transition, implemented either by Pool-Uniform or fixed-count Perm-Scan. Fixed-FpD combines the same fixed-count constructions with |ํฑ เฌด | = ํท/2. As shown in section 5.2.3, both variants attain the target mean overlap similarity and exact normalized Hamming similarity, although |ํฑ เฏค | need not remain fixed because the numbers of 1โ0/0โ1 flips are not constrained to be equal. A representative generator construction is illustrated in Figure 3. 17 Fixed-kpD additionally enforces exact balance with ํ = ํท/(2ํ) flips in each direction per transition. Block-Swap realizes this by complementing successive disjoint balanced blocks, whereas Float generates the levels by cyclic shifts of a contiguous half-one vector. Both preserve |ํฑ เฏค | = ํท/2 and realize ํ lin (ฮ) exactly in every realization. The quantities ํน and ํ are assumed to be integers where required. Figure 3. Linear-family Fixed-FpD Pool-Uniform generator construction. The example uses ํท =16, |ํฑ เฌด | = ํท/2=8, and two successive updates with |ํ เฌด | = |ํ เฌต |=ํน =4. Blue mask components are selected for flip; orange HV components change by XOR. Red positions in ํ เฌต were selected in ํ เฌด and are no longer eligible, illustrating the without-replacement rule. 6 Accuracy of Approximating the Target Similarity Laws This section summarizes exact finite-D expressions for ฮผ th (ํ,ํ), bias th (ํ,ํ), and v th (ํ,ํ) for the generators introduced earlier, relative to the target laws ํ exp and ํ lin defined in section 3. The corresponding RMSE th is obtained using the evaluation protocol of section 3.3 and compared with the experiments in section 7.2. Full derivations are provided in supplementary note 3, which mirrors the structure of this section. 6.1 Finite-D Accuracy for Exponential Similarity Family We analyze the SC scheme and the generator constructions introduced in section 4.3. For Baseline, Fixed-pD, Fixed-F, and Fixed-FpD, the finite-D formulas are expressed in terms of two one-step parameters, ฯ step and ฮณ step , which summarize the marginal and pair-wise behavior of a single transition. Fixed-kpD is handled separately via an overlap-moment recursion. Because ํ(ํ,ํ), bias th (ํ,ํ), and v th (ํ,ํ) are symmetric in (ํ,ํ), we assume ํ โค ํ, so that ฮ = |ํโํ| = ํโํ. 6.1.1 Finite-D Formulas and Variance Summary Let ํ เฏค โ1,...,D denote the index set flipped in the level transition (step) ํโํ+1, and use the ยฑ1 encoding ํฆ เฏค (ํ) := 2ํฅ เฏค (ํ)โ1. Define ํ เฏค (ํ) โ +1,โ1 by ํ เฏค (ํ) = โ1 iff ํ โ ํ เฏค and ํ เฏค (ํ) = +1 otherwise, so ํฆ เฏค+เฌต (ํ) = ํ เฏค (ํ)ํฆ เฏค (ํ). Define the one-step parameters (level and component permutation invariant) ฯ step := E[ํ เฏค (ํ)] and ฮณ step := E[ํ เฏค (ํ)ํ เฏค (ํ)] for ํ โ ํ. ฯ step determines the induced mean similarity profile ฮผ th (ํ,ํ), whereas ฮณ step captures within- 18 step dependence between distinct components and enters the finite-D variance. Independent within-step flips give ฮณ step = ฯ step เฌถ ; fixed-count flip selection generally does not. Mean similarity and bias. Across ฮ transitions, E[ํฆ เฏ (ํ)ํฆ เฏ (ํ)] = ฯ step ฮ . Global sign-flip symmetry at ํ = 1/2 implies E[ํฆ เฏค (ํ)] = 0. Hence ฮผ th (ํ,ํ) := E[ํ(ํ,ํ)] = 1/2+(1/2)ฯ step ฮ . For Baseline, Fixed-pD, Fixed-F, and Fixed-FpD, the marginal per-component flip probability is ํ, with ํ = ํน/ํท in the fixed-count variants. Hence ฯ step = E[ํ เฏค (ํ)] = 1โ2ํ=ฯ, so ฮผ th (ํ,ํ) = ํ exp (ฮ) and bias th (ํ,ํ) = 0. The complete derivation is given in supplementary note 3.2. Variance template. Define ํด เฏค := โ เฏ ํฆ เฏค (ํ) and ํถ ab := โ เฏ (ํฆ เฏ (ํ)ํฆ เฏ (ํ)). Then ํ(ํ,ํ) = โ เฏ ํฅ เฏ (ํ)ํฅ เฏ (ํ) = ํท/4+(ํด เฏ +ํด เฏ +ํถ ab )/4. Under the global sign flip Cov(ํด เฏ +ํด เฏ ,ํถ ab ) = 0, thus v th (ํ,ํ) := Var(ํ(ํ,ํ)) = (Var(ํด เฏ +ํด เฏ )+Var(ํถ ab )) / (4ํท เฌถ ). (6.1) Derivation shows that Var(ํถ ab ) = ํท(1โฯ step เฌถฮ )+ํท(ํทโ1)(ฮณ step ฮ โฯ step เฌถฮ ). (6.2) The variant-specific values of ฯ step , ฮณ step , and Var(ํด เฏ +ํด เฏ ) are summarized below, their derivations and a compact tabular summary are provided in supplementary note 3.2. For Bernoulli(1/2) initialization, ํฆ เฏค remains i.i.d. Rademacher across components, implying Cov(ํด เฏ ,ํด เฏ ) = ํทฯ step ฮ , and Var(ํด เฏ +ํด เฏ ) = 2ํท+2ํทฯ step ฮ . (6.3) For Baseline, ฯ step = 1โ2ํ and ฮณ step = ฯ step เฌถ . For Fixed-F, ฯ step = 1โ2ํน/ํท and ฮณ step = 1โ 4ํน(ํทโํน)/(ํท(ํทโ1)). Substitution into (6.1)-(6.3) gives v th (ํ,ํ). For |ํฑ เฌด | = ํท/2, we have E[ํฆ เฌด (ํ)] = 0 and E[ํฆ เฌด (ํ)ํฆ เฌด (ํ)] = โ1/(ํทโ1) for ํ โ ํ. Propagation through the level transitions gives Var(ํด เฏ +ํด เฏ ) = ํท(2โฮณ step เฏ โฮณ step เฏ +2ฯ step ฮ (1โฮณ step เฏ )). (6.4) Fixed-pD uses ฮณ step = ฯ step เฌถ , as in Baseline, whereas Fixed-FpD uses ฮณ step = 1โ4ํน(ํทโ ํน)/(ํท(ํทโ1)), as in Fixed-F. These provide Var(ํด เฏ +ํด เฏ ) and Var(ํถ ab ) to obtain v th (ํ,ํ). 6.1.2 Equal-Swap, Constant Hamming-Weight (Fixed-kpD) Fixed-kpD preserves |ํฑ เฏค | = ํท/2 at every level. With ํ := ํํท/2 we have ฯ step = 1โ 4ํ/ํท = 1โ2ํ = ฯ, so ฮผ th (ํ,ํ) = ํ exp (ฮ) and bias th (ํ,ํ) = 0. Because its equal-swap update samples from the current ones and zeros, the common (ฯ step , ฮณ step ) variance template does not apply. The finite-D variance derivation is given in supplementary note 3.2.4. 6.2 Finite-D Accuracy for Linear Similarity Family 19 For the deterministic equal-swap constructions Fixed-kpD Block-Swap and Float, ํ(ํ,ํ) = ํ lin (ฮ) in every realization, so bias th (ํ,ํ) = v th (ํ,ํ) = 0. For the remaining generators, let ํพ denote the number of distinct components flipped between levels ํ and ํ. In Fixed-F and Fixed-FpD, ํพ = ฮโํน is deterministic. In the random-count Baseline and Fixed-pD constructions, ํพ is random because the proposed update counts are truncated by the remaining- pool capacity. Thus, the fixed-count variants have no update-count induced terminal bias, whereas the random-count variants acquire terminal bias and an additional variance term through Var(ํพ). 6.2.1 Fixed-Count Linear Variants The Fixed-F and Fixed-FpD results apply to both Pool-Uniform and Perm-Scan. With integer ํน = ํท/ํ, both satisfy ฮผ th (ํ,ํ) = ํ lin (ฮ) and therefore have zero bias. For Fixed-F, Bernoulli(1/2) initialization yields v th (ํ,ํ) = (1โฮ/ํ)/ํท. Fixed-FpD has the same mean but a different finite-D variance because the constraint |ํฑ เฌด | = ํท/2 induces dependence across components; the resulting hypergeometric variance is derived in supplementary note 3.3. 6.2.2 Fixed-Order Random-Count Linear Variants For both Fixed-pD and Baseline random-count Perm-Scan constructions, E[ํ(ํ,ํ) | ํพ] = (ํทโํพ)/ํท, giving ฮผ th (ํ,ํ) = 1โE[ํพ]/ํท, bias th (ํ,ํ) = ฮ/ํโE[ํพ]/ํท. For Baseline, the variance can be written as v th (ํ,ํ) = (1โE[ํพ]/ํท)/ํท+Var(ํพ)/ํท เฌถ . For Fixed-pD, constant- weight initialization changes the conditional-overlap variance, while the same Var(ํพ)/ํท เฌถ term accounts for update-count variability. Under the Binomial proposed-count model, the required moments of ํพ, together with the additional cumulative-flip-count moments required for Fixed-pD, are evaluated at finite ํท. Full derivations are given in supplementary note 3.3. 7 Experimental Investigation This section validates the finite-D theory and illustrates the realized similarity profiles. Section 7.1 presents representative overlap-similarity profiles for the exponential and linear families, and section 7.2 compares empirical RMSE with the theoretical predictions. 7.1 Examples of Similarity Profiles Figure 4 shows representative exponential-family overlap-similarity profiles from three independent realizations for the five derandomization variants. Increasing derandomization generally produces smoother realized profiles, although the visual ordering does not exactly coincide with the RMSE ordering in section 7.2.1. Figure 5 shows representative linear-family overlap-similarity profiles from three independent realizations. The profiles become increasingly regular across the derandomization variants, with Fixed-kpD reproducing the linear target realization-wise by construction. Corresponding Hamming-similarity profiles and additional parameter settings are given in supplementary note 4.1. 20 (a) Overlap similarity, ํ = 0 . 01 ํท = 200 ํท = 10000 (b) (c) (d) (e) Comparison level ํ Figure 4: Exponential similarity profiles (2sim dot /ํท as a function of comparison level ํ) from three independent realizations, for anchors ํ โ 0,33,67,100. Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000, ํ = 0.01. 21 ํท = 200 ํท = 10000 (a) Overlap similarity (b) (c) (d) (e) Comparison level ํ Figure 5: Linear similarity profiles (2sim dot /ํท as a function of comparison level ํ) from three independent realizations, for anchors ํ โ 0,33,67,100. Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000. 22 7.2 RMSE of Similarity: Experiments versus Theory Using the error metrics of section 3.3, we compare empirical anchor-wise RMSE emp (ํ) with the theoretical predictions of section 6, using the same anchor-wise averaging convention. 7.2.1 Exponential Similarity Family For the exponential similarity family, Table 3 compares empirical and theoretical anchor-wise RMSE across the five derandomization variants and flip rates ํ. Additional parameter settings are reported in supplementary note 4.2. Table 3: Exponential similarity family: RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,33,67,100 and ํ โ 0.01,0.02,0.05,0.10,0.20. โMeanโ averages RMSE over anchors. Parameters: ํท = 200, ํ = 100, 10000 realizations. Theory rows follow the empirical rows for each generator. Variant Generator ํ ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline 0.01 0.066729 0.068688 0.068732 0.066715 0.067716 1 Baseline 0.02 0.064383 0.066804 0.066408 0.064496 0.065523 1 Baseline 0.05 0.062688 0.063955 0.064030 0.062906 0.063395 1 Baseline 0.10 0.061918 0.062556 0.062725 0.061906 0.062276 1 Baseline 0.20 0.061407 0.061920 0.061590 0.061625 0.061636 1 theory Baseline 0.01 0.067227 0.068927 0.068927 0.067227 0.068077 1 theory Baseline 0.02 0.064815 0.066910 0.066910 0.064815 0.065863 1 theory Baseline 0.05 0.062709 0.063995 0.063995 0.062709 0.063352 1 theory Baseline 0.10 0.061963 0.062581 0.062581 0.061963 0.062272 1 theory Baseline 0.20 0.061584 0.061828 0.061828 0.061584 0.061706 2 Fixed-pD 0.01 0.043314 0.059840 0.063591 0.063186 0.057483 2 Fixed-pD 0.02 0.046645 0.063938 0.065462 0.063563 0.059902 2 Fixed-pD 0.05 0.048522 0.063254 0.063321 0.062259 0.059339 2 Fixed-pD 0.10 0.049257 0.062440 0.062317 0.061459 0.058868 2 Fixed-pD 0.20 0.049650 0.061556 0.061756 0.061401 0.058591 2 theory Fixed-pD 0.01 0.043422 0.059677 0.063892 0.063620 0.057653 2 theory Fixed-pD 0.02 0.046737 0.063847 0.065379 0.063502 0.059866 2 theory Fixed-pD 0.05 0.048680 0.063414 0.063482 0.062187 0.059441 2 theory Fixed-pD 0.10 0.049308 0.062305 0.062305 0.061685 0.058901 2 theory Fixed-pD 0.20 0.049612 0.061671 0.061671 0.061426 0.058595 3 Fixed-F 0.01 0.065236 0.066440 0.066160 0.065170 0.065751 3 Fixed-F 0.02 0.063698 0.065025 0.065177 0.063354 0.064314 3 Fixed-F 0.05 0.062030 0.063253 0.062977 0.062050 0.062577 3 Fixed-F 0.10 0.061580 0.062353 0.061908 0.061800 0.061910 3 Fixed-F 0.20 0.061404 0.061330 0.061592 0.061491 0.061455 3 theory Fixed-F 0.01 0.065080 0.066281 0.066281 0.065080 0.065681 3 theory Fixed-F 0.02 0.063595 0.064844 0.064844 0.063595 0.064220 3 theory Fixed-F 0.05 0.062190 0.062978 0.062978 0.062190 0.062584 23 3 theory Fixed-F 0.10 0.061686 0.062032 0.062032 0.061686 0.061859 3 theory Fixed-F 0.20 0.061427 0.061516 0.061516 0.061427 0.061472 4 Fixed-FpD 0.01 0.040203 0.056592 0.061208 0.060877 0.054720 4 Fixed-FpD 0.02 0.044950 0.061525 0.063206 0.062512 0.058048 4 Fixed-FpD 0.05 0.048091 0.062148 0.062821 0.061915 0.058744 4 Fixed-FpD 0.10 0.048943 0.061676 0.061805 0.061831 0.058564 4 Fixed-FpD 0.20 0.049432 0.061582 0.061711 0.061210 0.058483 4 theory Fixed-FpD 0.01 0.040036 0.056655 0.061063 0.061370 0.054781 4 theory Fixed-FpD 0.02 0.045039 0.061704 0.063273 0.062263 0.058070 4 theory Fixed-FpD 0.05 0.048013 0.062391 0.062459 0.061666 0.058632 4 theory Fixed-FpD 0.10 0.048961 0.061755 0.061755 0.061408 0.058470 4 theory Fixed-FpD 0.20 0.049418 0.061359 0.061359 0.061270 0.058352 5 Fixed-kpD 0.01 0.025899 0.019695 0.019470 0.025707 0.022693 5 Fixed-kpD 0.02 0.030873 0.026307 0.026179 0.030932 0.028573 5 Fixed-kpD 0.05 0.033549 0.031673 0.031762 0.033659 0.032661 5 Fixed-kpD 0.10 0.034446 0.033597 0.033652 0.034553 0.034062 5 Fixed-kpD 0.20 0.034872 0.034479 0.034534 0.034927 0.034703 5 theory Fixed-kpD 0.01 0.025729 0.019508 0.019508 0.025729 0.022619 5 theory Fixed-kpD 0.02 0.030663 0.026237 0.026237 0.030663 0.028450 5 theory Fixed-kpD 0.05 0.033551 0.031749 0.031749 0.033551 0.032650 5 theory Fixed-kpD 0.10 0.034458 0.033628 0.033628 0.034458 0.034043 5 theory Fixed-kpD 0.20 0.034893 0.034513 0.034513 0.034893 0.034703 Across all variants and flip rates, the theoretical predictions closely match the experimental RMSE values in both magnitude and anchor dependence. Anchor-averaged RMSE follows the ordering Baseline โ Fixed-F > Fixed-pD > Fixed-FpD > Fixed-kpD. The reduction from Baseline and Fixed-F to the constant-weight variants reflects the removal of random initial Hamming-weight imbalance, while Fixed-kpD gives the lowest RMSE, reflecting its additional equal-swap constraint and Hamming-weight preservation. Anchor dependence differs across variants. For Baseline and Fixed-F, interior anchors contain a larger proportion of small-separation comparisons and exhibit slightly larger RMSE than endpoint anchors. For Fixed-pD and Fixed-FpD, fixing the Hamming weight of the initial HV suppresses variability at ํ = 0, producing a noticeably smaller RMSE there. For Fixed- kpD, the per-separation error is larger at greater separations; consequently, endpoint anchors, which contain a larger proportion of large-separation comparisons, have larger RMSE than interior anchors. The anchor-to-anchor spread generally narrows as ํ increases, consistent with the faster approach of the separation-dependent variance terms to their long-separation regime. A detailed interpretation of these trends in terms of the finite-D variance expressions of section 6 and supplementary note 3 is given in supplementary note 4.2.2. 7.2.2 Linear Similarity Family 24 For the linear similarity family, Table 4 compares empirical and theoretical RMSE and reports bias for the random-count variants. Additional parameter settings are reported in supplementary note 4.2.3. Table 4: Linear similarity family: RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,33,67,100. Parameters: ํท = 200, ํ = 100, 10000 realizations. Bias is reported for Baseline and Fixed- pD. Theory rows follow the empirical rows for each generator. RMSE Variant Generator ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline (Pool-Bernoulli) 0.068781 0.069788 0.070744 0.069581 0.069723 1 Baseline (Perm-Scan) 0.068995 0.070054 0.071395 0.070264 0.070177 1 theory Baseline (Perm-Scan) 0.069250 0.070040 0.070765 0.070162 0.070054 2 Fixed-pD (Pool-Bernoulli) 0.055733 0.066032 0.066322 0.057171 0.061315 2 Fixed-pD (Perm-Scan) 0.055820 0.066006 0.066568 0.058288 0.061670 2 theory Fixed-pD (Perm-Scan) 0.055793 0.065745 0.066428 0.058055 0.061505 3 Fixed-F (Pool-Uniform) 0.049807 0.059829 0.059734 0.049916 0.054822 3 Fixed-F (Perm-Scan) 0.050224 0.060341 0.059971 0.049781 0.055079 3 theory Fixed-F (Perm-Scan) 0.050000 0.059955 0.059955 0.050000 0.054977 4 Fixed-FpD (Pool-Uniform) 0.028929 0.055150 0.055760 0.028929 0.042192 4 Fixed-FpD (Perm-Scan) 0.028658 0.054637 0.054938 0.028658 0.041723 4 theory Fixed-FpD (Perm-Scan) 0.028795 0.055139 0.055139 0.028795 0.041967 5 Fixed-kpD (Block-Swap) 0.000000 0.000000 0.000000 0.000000 0.000000 5 Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 5 theory Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 Bias Variant Generator ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline (Pool-Bernoulli) 0.004456 0.004539 0.004679 0.026600 0.010068 1 Baseline (Perm-Scan) 0.004720 0.004712 0.004735 0.027312 0.010370 1 theory Baseline (Perm-Scan) 0.004726 0.004726 0.004726 0.027148 0.010331 2 Fixed-pD (Pool-Bernoulli) 0.004493 0.004462 0.004488 0.025736 0.009795 2 Fixed-pD (Perm-Scan) 0.004697 0.004786 0.004767 0.027507 0.010439 2 theory Fixed-pD (Perm-Scan) 0.004726 0.004726 0.004726 0.027148 0.010331 The theoretical predictions closely match the corresponding experiments in both RMSE magnitude and anchor dependence. The anchor-averaged RMSE decreases in the order Baseline > Fixed-pD > Fixed-F > Fixed-FpD > Fixed-kpD. The fixed-count variants are essentially unbiased, whereas the random-count variants exhibit nonzero terminal bias near level ํ. Fixed-kpD matches the linear target exactly, giving zero bias and variance. 25 Anchor dependence also differs across variants. Fixed-F and Fixed-FpD have lower RMSE at endpoint anchors than at interior anchors, with the endpoint reduction stronger for Fixed-FpD. For Baseline and Fixed-pD, the terminal boundary increases bias while reducing the remaining run-to-run variability; constant-weight initialization lowers the overall RMSE of Fixed-pD relative to Baseline. A detailed interpretation of these trends using the finite-D formulas of section 6 is given in supplementary note 4.2.4. 8 General Discussion This section synthesizes the theoretical and empirical results into a mechanism-level account of scalar-codebook accuracy. We then use this account to derive generator-design implications and to identify limitations and directions for further work. 8.1 Mechanisms of Derandomization The results show that scalar-codebook derandomization acts by constraining distinct sources of stochastic variability in the level-transition process. This motivates separating three objects: the prescribed target similarity law, the derandomization variant, and the generator construction. The target law specifies the desired dependence of similarity on level separation; the variant specifies which sources of randomness are constrained; and the generator specifies how those constraints are implemented through component selection, update rules, reuse, and capacity handling. This separation is essential because matching the induced mean similarity profile does not determine finite-D accuracy: generators with the same mean profile can retain different dependence structures and therefore different variance, RMSE, anchor dependence, and terminal behavior. The derandomization variants clarify how distinct sources of variability are controlled. Constant-Hamming-weight initialization removes random-start imbalance in the initial HV. Fixing the update count additionally removes update-count variability, but does not eliminate fluctuations in the balance between 1โ0 and 0โ1 updates. Equal-swap updates impose this additional balance constraint and preserve Hamming weight at every level. These constraints are therefore complementary rather than interchangeable: each suppresses a different source of finite-D variability, and its effect on accuracy depends on which source dominates for the similarity family and parameter regime under consideration. The variants should therefore be viewed as controlling distinct constraint axes rather than as differing only in an overall degree of derandomization: Fixed-pD and Fixed-F isolate initialization and update-count control, respectively, whereas Fixed-FpD combines these controls and Fixed-kpD additionally enforces transition balance. Their relative effect on accuracy depends on the similarity family and operating regime. The generator construction determines the dependence that remains after these constraints are imposed. Selection rules control component reuse and across-component 26 dependence, update rules determine how selected components change state, and capacity handling determines the behavior when the eligible component pool becomes small. The distinction between the exponential and linear families illustrates the consequences. In the exponential family, with-replacement reuse produces the geometric induced mean profile, while the derandomization constraints primarily modify finite-D variability. In the linear family, without-replacement updates produce the linear dependence on separation, but the shrinking component pool introduces an additional finite-capacity effect. Random-count constructions can therefore develop terminal deviations even when their nominal update rule is calibrated to the target law. This view also explains why different constructions within the same derandomization variant need not be statistically equivalent. Remaining-pool Bernoulli thinning and fixed-order proposed-count selection, for example, both implement random-count without-replacement updates, but they handle finite remaining capacity differently near pool exhaustion and can consequently produce different bias and variance. Taken together, the results reveal a hierarchy of mechanisms: single-component transition statistics govern the induced mean profile, dependence structures govern much of the finite-D variability, and finite-capacity effects can introduce additional systematic terminal bias. This hierarchy provides a more informative basis for generator design than mean target matching alone. 8.2 Accuracy and Design Implications The results distinguish several levels of similarity-law matching. For the exponential SC constructions, fixing the marginal per-component flip probability fixes the induced mean decay, so different variants can share the same mean similarity profile while retaining different finite-D variability. For the linear fixed-count constructions, mean overlap similarity matches the target when ํน=ํท/ํ, while normalized Hamming similarity matches it realization-wise; the deterministic equal-swap constructions achieve realization-wise matching for both similarities. Thus, mean and realization-wise target matching are distinct design properties and should not be conflated when assessing scalar-codebook accuracy. Importantly, deviations from the target mean are themselves informative: in the linear random-count constructions they arise from the interaction between stochastic update counts and finite remaining capacity, with fixed-order truncation producing an upward terminal bias. Finite-D accuracy therefore requires more than analysis of the mean profile. The biasโ varianceโRMSE decomposition reveals that similar RMSE values can arise from different error compositions: a constraint may reduce realization-to-realization variance without changing the mean, whereas finite-capacity truncation in linear random-count constructions can introduce systematic terminal bias. Derandomization can therefore change not only the magnitude of the approximation error but also the balance between its stochastic and systematic components. The same analysis explains why accuracy depends on reference scalar level. Reference- level RMSE averages comparisons over different distributions of separations and, in the linear 27 family, over different degrees of exposure to the terminal boundary. In the exponential family, the resulting reference-level dependence is governed mainly by the separation dependence in the finite-D variance and by whether initialization is Bernoulli or constant-Hamming-weight. In the linear family, this effect is supplemented by depletion of the remaining component pool and the associated finite-capacity corrections. The close agreement between these theoretical predictions and the simulations across the tested settings indicates that the observed anchor effects are structured consequences of the generator mechanisms rather than incidental simulation fluctuations. The agreement between theory and simulation across the tested dimensions, quantization ranges, anchors, similarity families, variants, and constructions supports a mechanism-based design principle: generator selection should be governed by the dominant error source in the intended operating regime rather than by a universal ranking of derandomization strength. Constant-Hamming-weight initialization is effective when random- start imbalance is important; fixed-count updates are useful when update-count variability dominates; and equal-swap updates are required when Hamming-weight drift must be eliminated. For linear random-count constructions, finite-capacity effects must additionally be considered when the application emphasizes levels near the end of the quantization range. More generally, the appropriate construction is the least restrictive one that controls the error sources relevant to the intended operating regime, since additional constraints target specific stochastic mechanisms rather than providing a uniform improvement under all conditions. For practical use, Table 5 summarizes target-law matching and finite-D accuracy across the considered derandomization variants in the exponential and linear families. 28 Table 5. Target-law matching and finite-D accuracy of the five presented derandomization variants. Variant definitions are given in Section 3.1; the exponential and linear generator constructions are described in Sections 4.3 and 5.3, respectively, and their finite-D accuracy is analyzed in Sections 6.1 and 6.2. The exponential-family entries refer to the SC constructions; exact linear-family statements assume the integer conditions stated in Section 5. Variant Exponential similarity family Linear similarity family Baseline Mean overlap similarity matches the exponential target, so bias is zero. Random initialization and random update masks produce nonzero overlap-similarity variance and RMSE. Constructions: Pool-Bernoulli; random- count Perm-Scan. Near pool exhaustion, mean overlap similarity lies above the linear target, producing upward terminal bias. Overlap- similarity variance and RMSE are nonzero; Perm-Scan has a slightly larger terminal bias than Pool-Bernoulli. Fixed- pD Mean overlap similarity matches the exponential target, so bias is zero. Constant-Hamming-weight initialization removes random-start imbalance, but random update masks produce nonzero overlap-similarity variance and RMSE. Constructions: Pool-Bernoulli; random- count Perm-Scan. Near pool exhaustion, mean overlap similarity lies above the linear target, producing upward terminal bias. Constant- Hamming-weight initialization removes random-start imbalance, but overlap- similarity variance and RMSE remain nonzero; Perm-Scan has a slightly larger terminal bias than Pool-Bernoulli. Fixed- F Mean overlap similarity matches the exponential target, so bias is zero. Fixed update counts remove update- count variability, but Bernoulli initialization and random fixed-count masks produce nonzero overlap- similarity variance and RMSE. Constructions: Pool-Uniform; fixed-count Perm-Scan. Mean overlap similarity matches the linear target, so bias is zero, and normalized Hamming similarity matches the linear target exactly in every realization. Overlap- similarity variance and RMSE remain nonzero. Fixed- FpD Mean overlap similarity matches the exponential target, so bias is zero. Constant-Hamming-weight initialization and fixed update counts remove random-start imbalance and update-count variability, but random fixed-count masks produce nonzero overlap-similarity variance and RMSE. Constructions: Pool-Uniform; fixed-count Perm-Scan. Mean overlap similarity matches the linear target, so bias is zero, and normalized Hamming similarity matches the linear target exactly in every realization. Constant- Hamming-weight initialization removes random-start imbalance, but overlap- similarity variance and RMSE remain nonzero. Fixed- kpD Mean overlap similarity matches the exponential target, so bias is zero. Equal-swap updates preserve Hamming weight at every level, but random selection of the swapped components produces nonzero overlap-similarity variance and RMSE. Constructions: Block-Swap; Float. Overlap similarity and normalized Hamming similarity match the linear target exactly in every realization. Bias, variance, and RMSE are zero. 29 8.3 Limitations and Future Directions The present analysis focuses on dense binary scalar codebooks and on exponential and linear target-similarity families. Other HV representations and similarity laws may change both the relevant similarity statistics and the dependence induced by the generator mechanisms. An important direction is therefore to determine which elements of the proposed mechanism-level framework generalize across representations and target laws, and which require representation- specific finite-D analyses. The theory also isolates the scalar-codebook layer rather than the complete HDC pipeline. In practical systems, scalar HVs undergo binding or permutation, aggregation, and downstream similarity or classification operations. Future work should therefore establish how scalar-level bias, variance, reference-level dependence, and boundary effects propagate through these transformations, including whether aggregation suppresses them, preserves them, or creates interactions with other sources of representation variability. The exact finite-D random-count variance theory developed here applies to the fixed- order Perm-Scan construction. For adaptive Pool-Bernoulli, Proposition 1 gives the exact mean recursion and hence the bias, but a corresponding finite-D variance and RMSE theory for its state-dependent remaining-pool dynamics is not developed here. Extending the variance analysis to this construction would complete the theoretical comparison of the random-count mechanisms. 9 Conclusions This paper developed a unified derandomization framework for dense binary scalar codebooks in hyperdimensional computing. The framework treats scalar codebook generation as a sequence of level transitions and separates three aspects that are often conflated: the target similarity law, the derandomization constraints, and the concrete generator construction. This separation makes it possible to analyze exponential and linear target-similarity families within a common transition-based view, while still explaining why generators with the same target law or the same derandomization variant can differ at finite dimension. Derandomization in this setting is mechanism-specific control of finite-dimensional error rather than a single generic reduction of randomness. Constant Hamming-weight initialization removes random-start imbalance; fixed update counts remove update-count variability; and exact balance constraints prevent Hamming-weight drift. These constraints affect different parts of the error, so additional constraints are useful when they target the error source that dominates in the intended operating regime. The generator-construction view further explains the remaining deviations from the target law. Selection rules, update mechanisms, dependence within a transition, and truncation or capacity handling determine bias, variance, reference-level effects, and boundary behavior. In particular, finite-capacity effects in the linear family and dependence induced by fixed-count 30 or balanced updates cannot be inferred from the target similarity law alone. This is why mean target matching, although important, is not sufficient to characterize the finite-dimensional accuracy of a scalar codebook generator. The finite-dimensional theory derived in this paper connects these mechanisms to induced mean similarity, bias, variance, and RMSE, and the simulations validate the predicted trends across similarity families, dimensions, quantization ranges, reference scalar levels, variants, and generator constructions. The resulting design rule is mechanism-specific: choose the target similarity law, identify whether the dominant finite-dimensional error arises from random-start imbalance, update-count variability, Hamming-weight drift, within-transition dependence, or finite-capacity effects, and match the derandomization mechanism to the dominant source of finite-dimensional error while respecting implementation constraints. Acknowledgments The work of D.R. was supported in part by the Swedish Foundation for Strategic Research (SSF, grant nos. UKR22-0024, UKR24-0014). The work of E.O. and D.R. was supported in part by the Swedish Research Council (VR grant no. 2022-04657). The work of E.O. was supported in part by STINT, the Swedish Foundation for International Cooperation in Research and Education (STINT, grant no. MG2020-8842) and Intel Neuromorphic Research Community Project: Unsupervised learning in NLP tasks on using Vector-Symbolic representations on phasor-based associative memory. D.K. acknowledges funding from the Swedish Strategic Research Foundation under the Future Research Leaders program (Grant No. FFL24-0111) and the Swedish Research Council under the Starting Grant program (Grant No. 2025-05421). This work was supported in part by the AFOSR under award number FA8655-25-1-7007. V.S. acknowledges funding from European Union under the REFRESH project number CZ.10.03.01/00/22 /0000048 via the Operational Programme Just Transition; CLARA project under European Unionโs HORIZON EUROPE No 101136607. E.O. and D.R. acknowledge the computational resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725, as well as help and support of Tim Ufer and Philip Gard. 31 References Alameda, J. S., Bang, C., Brennan, Z., Herzog, D. P., Kritschgau, J., & Sprangel, E. (2024). Cutoff in the Bernoulli-Laplace urn model with swaps of order n. Electronic Communications in Probability, 29, article no. 2, 1-13. https://doi.org/10.1214/23- ECP569 Aygun, S., Moghadam, M. S., Najafi, M. H., & Imani, M. (2023). Learning from Hypervectors: A Survey on Hypervector Encoding (arXiv:2308.00685). arXiv. https://doi.org/10.48550/arXiv.2308.00685 Chen, G.-Y., Fang, Y.-J., & Sheu, Y.-C. (2012). The cutoff phenomenon for Ehrenfest chains. Stochastic Processes and Their Applications, 122(8), 2830โ2853. https://doi.org/10.1016/j.spa.2012.05.003 Chen, G.-Y., & Kumagai, T. (2018). Cutoffs for product chains. Stochastic Processes and Their Applications, 128(11), 3840โ3879. https://doi.org/10.1016/j.spa.2018.01.002 Clarkson, K. L., Ubaru, S., & Yang, E. (2023). Capacity Analysis of Vector Symbolic Architectures (arXiv:2301.10352). arXiv. https://doi.org/10.48550/arXiv.2301.10352 Cohen, T., Widdows, D., Wahle, M., & Schvaneveldt, R. (2013). Orthogonality and Orthography: Introducing Measured Distance into Semantic Space. Selected Papers of the 7th International Conference on Quantum Interaction - Volume 8369, QI 2013, 34โ 46. https://doi.org/10.1007/978-3-642-54943-4_4 Dewulf, P., De Baets, B., & Stock, M. (2025). The hyperdimensional transform for distributional modeling, regression and classification. Neural Computing and Applications, 37(23), 19393โ19422. https://doi.org/10.1007/s00521-025-11405-0 Diaconis, P. (2009). The Markov chain Monte Carlo revolution. Bulletin of the American Mathematical Society, 46(2), 179โ205. https://doi.org/10.1090/S0273-0979-08-01238- X Diaconis, P., Graham, R. L., & Morrison, J. A. (1990). Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures & Algorithms, 1(1), 51โ72. https://doi.org/10.1002/rsa.3240010105 Diaconis, P., & Saloff-Coste, L. (1993). Comparison Theorems for Reversible Markov Chains. The Annals of Applied Probability, 3(3), 696โ730. https://doi.org/10.1214/aoap/1177005359 Diaconis, P., & Shahshahani, M. (1987). Time to Reach Stationarity in the BernoulliโLaplace Diffusion Model. SIAM Journal on Mathematical Analysis, 18(1), 208โ218. https://doi.org/10.1137/0518016 Diaconis, P., & Stroock, D. (1991). Geometric Bounds for Eigenvalues of Markov Chains. The Annals of Applied Probability, 1(1), 36โ61. https://w.jstor.org/stable/2959624 32 Donnelly, P., Lloyd, P., & Sudbury, A. (1994). Approach to Stationarity of the Bernoulliโ Laplace Diffusion Model. Advances in Applied Probability, 26(3), 715โ727. https://doi.org/10.2307/1427817 Eskenazis, A., & Nestoridi, E. (2020). Cutoff for the Bernoulli-Laplace urn model with o(n) swaps. Annales de lโInstitut Henri Poincarรฉ, Probabilitรฉs et Statistiques, 56(4), 2621โ 2639. https://doi.org/10.1214/20-AIHP1052 Fill, J. A. (1991). Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process. The Annals of Applied Probability, 1(1), 62โ87. https://w.jstor.org/stable/2959625 Gayler, R. W. (1998). Multiplicative Binding, Representation Operators & Analogy. Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences. https://web- archive.southampton.ac.uk/cogprints.org/502/ Gayler, R. W. (2004). Vector Symbolic Architectures answer Jackendoffโs challenges for cognitive neuroscience (arXiv:cs/0412059). arXiv. https://doi.org/10.48550/arXiv.cs/0412059 Ge, L., & Parhi, K. K. (2020). Classification Using Hyperdimensional Computing: A Review. IEEE Circuits and Systems Magazine, 20(2), 30โ47. https://doi.org/10.1109/MCAS.2020.2988388 Haputhanthri, D., De Silva, D., Osipov, E., Rachkovskij, D., & Gayler, R. W. (2026). Parametrization of sparse distributed representations for vector data classification. Neurocomputing, 678, 133168. https://doi.org/10.1016/j.neucom.2026.133168 Healy, M. J., & Caudell, T. P. (1997). Acquiring rule sets as a product of learning in a logical neural architecture. IEEE Transactions on Neural Networks, 8(3), 461โ474. https://doi.org/10.1109/72.572088 Hsiao, Y.-R., Chuang, Y.-C., Chang, C.-Y., & Wu, A.-Y. (2021). Hyperdimensional Computing with Learnable Projection for User Adaptation Framework. In I. Maglogiannis, J. Macintyre, & L. Iliadis (Eds.), Artificial Intelligence Applications and Innovations (Vol. 627, p. 436โ447). Springer International Publishing. https://doi.org/10.1007/978-3-030-79150-6_35 Huang, C.-T., Chang, C.-Y., Chuang, Y.-C., & Wu, A.-Y. (Andy). (2021). PQ-HDC: Projection-Based Quantization Scheme for Flexible and Efficient Hyperdimensional Computing. 425โ435. https://doi.org/10.1007/978-3-030-79150-6_34 Jackel, L. D., Howard, R. E., Denker, J. S., Hubbard, W., & Solla, S. A. (1987). Building a hierarchy with neural networks: An example - image vector quantization. Applied Optics, 26(23), 5081โ5084. https://doi.org/10.1364/ao.26.005081 Kahawala, S., De Silva, D., Osipov, E., Rachkovskij, D., & Gayler, R. W. (2026). Graph vector function architecture. Neural Networks, 197, 108416. https://doi.org/10.1016/j.neunet.2025.108416 33 Kanerva, P. (1994). The Spatter Code for Encoding Concepts at Many Levels. ICANN 1994. https://doi.org/10.1007/978-1-4471-2097-1_52 Kanerva, P. (1996). Binary Spatter-Coding of Ordered K-Tuples. Proceedings of the 1996 International Conference on Artificial Neural Networks, ICANN 96, 869โ873. Kanerva, P. (2009). Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors. Cognitive Computation, 1(2), 139โ159. https://doi.org/10.1007/s12559-009-9009-8 Kleyko, D., Davies, M., Frady, E. P., Kanerva, P., Kent, S. J., Olshausen, B. A., Osipov, E., Rabaey, J. M., Rachkovskij, D. A., Rahimi, A., & Sommer, F. T. (2022). Vector Symbolic Architectures as a Computing Framework for Emerging Hardware. Proceedings of the IEEE, 110(10), 1538โ1571. https://doi.org/10.1109/JPROC.2022.3209104 Kleyko, D., Kheffache, M., Frady, E. P., Wiklund, U., & Osipov, E. (2021). Density Encoding Enables Resource-Efficient Randomly Connected Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32(8), 3777โ3783. https://doi.org/10.1109/TNNLS.2020.3015971 Kleyko, D., Rachkovskij, D. A., Osipov, E., & Rahimi, A. (2022). A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations. ACM Comput. Surv., 55(6), 130:1-130:40. https://doi.org/10.1145/3538531 Kleyko, D., Rachkovskij, D., Osipov, E., & Rahimi, A. (2023). A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Applications, Cognitive Models, and Challenges. ACM Comput. Surv., 55(9), 175:1-175:52. https://doi.org/10.1145/3558000 Kleyko, D., Rahimi, A., Rachkovskij, D. A., Osipov, E., & Rabaey, J. M. (2018). Classification and Recall With Binary Hyperdimensional Computing: Tradeoffs in Choice of Density and Mapping Characteristics. IEEE Transactions on Neural Networks and Learning Systems, 29(12), 5880โ5898. https://doi.org/10.1109/TNNLS.2018.2814400 Kussul, E. M., Baidyk, T. N., Lukovich, V. V., & Rachkovskij, D. A. (1993). Adaptive neural network classifier with multifloat input coding. NEUROโ93, 209โ216. Kussul, E. M., Rachkovskij, D. A., & Baidyk, T. N. (1991a). Associative-projective neural networks: Architecture, implementation, applications. Fourth International Conference โNeural Networks and Their Applications,โ 463โ476. https://w.researchgate.net/profile/Dmitri- Rachkovskij/publication/341735137_Associative- projective_neural_networks_architecture_implementation_applications/links/5ed111c 8299bf1c67d271fa2/Associative-projective-neural-networks-architecture- implementation-applications.pdf 34 Kussul, E. M., Rachkovskij, D. A., & Baidyk, T. N. (1991b). On image texture recognition by associative-projective neurocomputer. Intelligent Engineering Systems through Artificial Neural Networks, 453โ458. Laiho, M., Poikonen, J. H., Kanerva, P., & Lehtonen, E. (2015). High-dimensional computing with sparse vectors. 2015 IEEE Biomedical Circuits and Systems Conference (BioCAS), 1โ4. https://doi.org/10.1109/BioCAS.2015.7348414 Masum, A. K. M., Moghadam, M. S., Moon, S. H., Ahmed, A. M. M., Najafi, M. H., Reis, D., & Aygun, S. (2025). Late Breaking Results: On-the-Fly Hadamard Hypervector Processing for Efficient Hyperdimensional Computing. 2025 62nd ACM/IEEE Design Automation Conference (DAC), 1โ2. https://doi.org/10.1109/DAC63849.2025.11133357 Moghadam, M. S., Aygun, S., Banitaba, F. S., & Najafi, M. H. (2024). All You Need is Unary: End-to-End Unary Bit-stream Processing in Hyperdimensional Computing. Proceedings of the 29th ACM/IEEE International Symposium on Low Power Electronics and Design, ISLPED โ24, 1โ6. https://doi.org/10.1145/3665314.3670834 Moghadam, M. S., Masum, A. K. M., Aygun, S., & Najafi, M. H. (2025). Robust Data Processing for Vector Symbolic Computing. Proceedings of the Great Lakes Symposium on VLSI 2025, GLSVLSI โ25, 823โ828. https://doi.org/10.1145/3716368.3735287 Nestoridi, E. (2017). A Non-Local Random Walk on the Hypercube. Advances in Applied Probability, 49(4), 1288โ1299. https://doi.org/10.1017/apr.2017.42 Neubert, P., Schubert, S., & Protzel, P. (2019). An Introduction to Hyperdimensional Computing for Robotics. KI - Kรผnstliche Intelligenz, 33(4), 319โ330. https://doi.org/10.1007/s13218-019-00623-z Penz, P. A. (1987). The closeness code: An input integer to binary vector transformation suitable for neural network algorithms. Proceedings of IEEE First International Conference on Neural Networks, 515โ522. Plate, T. A. (1995). Holographic reduced representations. IEEE Transactions on Neural Networks, 6(3), 623โ641. https://doi.org/10.1109/72.377968 Plate, T. A. (2000). Analogy retrieval and processing with distributed vector representations. Expert Systems, 17(1), 29โ40. https://doi.org/10.1111/1468-0394.00125 Plate, T. A. (2003). Holographic Reduced Representation: Distributed Representation for Cognitive Structures. CSLI Publications. Purdy, S. (2016). Encoding Data for HTM Systems (arXiv:1602.05925). arXiv. https://doi.org/10.48550/arXiv.1602.05925 Rachkovskij, D. A. (2001). Representation and processing of structures with binary sparse distributed codes. IEEE Transactions on Knowledge and Data Engineering, 13(2), 261โ276. https://doi.org/10.1109/69.917565 35 Rachkovskij, D. A. (2024). Shift-Equivariant Similarity-Preserving Hypervector Representations of Sequences. Cognitive Computation, 16(3), 909โ923. https://doi.org/10.1007/s12559-024-10258-4 Rachkovskij, D. A., & Fedoseyeva, T. V. (1990). On audio signals recognition by multilevel neural network. Proceedings of The International Symposium on Neural Networks and Neural Computing, 281โ283. https://w.researchgate.net/publication/341966170_On_audio_signals_recognition_ by_multilevel_neural_network Rachkovskij, D. A., & Kleyko, D. (2022). Recursive Binding for Similarity-Preserving Hypervector Representations of Sequences. 2022 International Joint Conference on Neural Networks (IJCNN), 1โ8. https://doi.org/10.1109/IJCNN55064.2022.9892462 Rachkovskij, D. A., & Kussul, E. M. (2001). Binding and Normalization of Binary Sparse Distributed Representations by Context-Dependent Thinning. Neural Computation, 13(2), 411โ452. https://doi.org/10.1162/089976601300014592 Rachkovskij, D. A., Kussul, E. M., & Baidyk, T. N. (2013). Building a world model with structure-sensitive sparse binary distributed representations. Biologically Inspired Cognitive Architectures, 3, 64โ86. https://doi.org/10.1016/j.bica.2012.09.004 Rachkovskij, D. A., Slipchenko, S. V., Kussul, E. M., & Baidyk, T. N. (2005). Sparse Binary Distributed Encoding of Scalars. Journal of Automation and Information Sciences, 37(6), 12โ23. https://doi.org/10.1615/J%20Automat%20Inf%20Scien.v37.i6.20 Rachkovskij, D. A., Slipchenko, S. V., Misuno, I. S., Kussul, E. M., & Baidyk, T. N. (2005). Sparse Binary Distributed Encoding of Numeric Vectors. Journal of Automation and Information Sciences, 37(11), 47โ61. https://doi.org/10.1615/J%20Automat%20Inf%20Scien.v37.i11.60 Rahimi, A., Benatti, S., Kanerva, P., Benini, L., & Rabaey, J. M. (2016). Hyperdimensional biosignal processing: A case study for EMG-based hand gesture recognition. 2016 IEEE International Conference on Rebooting Computing (ICRC), 1โ8. https://doi.org/10.1109/ICRC.2016.7738683 Raviv, N. (2024). Linear Codes for Hyperdimensional Computing. Neural Computation, 36(6), 1084โ1120. https://doi.org/10.1162/neco_a_01665 Reimann, S. (2025). Memory States From Almost Nothing: Representing and Computing in a Nonassociative Algebra. Neural Computation, 37(6), 1154โ1170. https://doi.org/10.1162/neco_a_01755 Roodsari, M. S., Krautter, J., & Tahoori, M. (2024). OTFGEncoder - HDC: Hardware-efficient Encoding Techniques for Hyperdimensional Computing. 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE), 1โ2. https://doi.org/10.23919/DATE58400.2024.10546523 36 Smets, L., Rachkovskij, D., Osipov, E., Van Leekwijck, W., Volkov, O., & Latrรฉ, S. (2025). Margin-Based Training of HDC Classifiers. Big Data and Cognitive Computing, 9(3), Article 3. https://doi.org/10.3390/bdcc9030068 Smets, L., Rachkovskij, D., Osipov, E., Volkov, O., Van Leekwijck, W., & Latrรฉ, S. (2025). Classification Performance of Confidence-Driven Centroids. Cybernetics and Systems Analysis, 61(2), 289โ304. https://doi.org/10.1007/s10559-025-00768-w Smets, L., Van Leekwijck, W., Tsang, I. J., & Latrรฉ, S. (2023). Training a Hyperdimensional Computing Classifier Using a Threshold on Its Confidence. Neural Computation, 35(12), 2006โ2023. https://doi.org/10.1162/neco_a_01618 Smith, D., & Stanford, P. (1990). A random walk in Hamming space. 1990 IJCNN International Joint Conference on Neural Networks, 2, 465โ470. https://doi.org/10.1109/IJCNN.1990.137756 Stock, M., Van Criekinge, W., Boeckaerts, D., Taelman, S., Van Haeverbeke, M., Dewulf, P., & De Baets, B. (2024). Hyperdimensional computing: A fast, robust, and interpretable paradigm for biological data. PLOS Computational Biology, 20(9), e1012426. https://doi.org/10.1371/journal.pcbi.1012426 Thomas, A., Dasgupta, S., & Rosing, T. (2021). A Theoretical Perspective on Hyperdimensional Computing. Journal of Artificial Intelligence Research, 72, 215โ 249. https://doi.org/10.1613/jair.1.12664 Thomas, A., Khaleghi, B., Jha, G. K., Dasgupta, S., Himayat, N., Iyer, R., Jain, N., & Rosing, T. (2023). Streaming Encoding Algorithms for Scalable Hyperdimensional Computing (arXiv:2209.09868). arXiv. https://doi.org/10.48550/arXiv.2209.09868 Vergรฉs, P., Givargis, T., & Nicolau, A. (2023). RefineHD: Accurate and Efficient Single-Pass Adaptive Learning Using Hyperdimensional Computing. 2023 IEEE International Conference on Rebooting Computing (ICRC), 1โ8. https://doi.org/10.1109/ICRC60800.2023.10386671 Widdows, D., & Cohen, T. (2015). Reasoning with vectors: A continuous model for fast robust inference. Logic Journal of the IGPL, 23(2), 141โ173. https://doi.org/10.1093/jigpal/jzu028 37 1 Supplementary Note 1: Exponential Similarity Family 1.1 SubtractโAdd 1.1.1 Derivation of Mean Between-Level Similarity (SubtractโAdd) Fix an anchor level ํ and let ํ เฏค := Pr(ํ เฏ+เฏค = 1, ํ เฏ = 1), ํ โฅ 0, so ํ is the level separation from the anchor, ํ = ฮ. In one SA transition, Degrade flips a current 1 to 0 with probability ํ; Refill then flips each current 0 after Degrade to 1 with probability ฮฑ. We choose ฮฑ = ํ/(1+ํ), because this preserves ํ = 1/2. Let us write a recursion for ํ เฏค . Before the DegradeโRefill transition from level ํ+ํ to ํ+ํ+1, we have Pr(ํ เฏ+เฏค = 1) = 1/2, Pr(ํ เฏ+เฏค = 0) = 1/2. The joint probabilities for (ํ เฏ+เฏค ,ํ เฏ ) are as follows. (1,1): ํ เฏค ; (1,0): 1/2โํ เฏค , because Pr(ํ เฏ+เฏค = 1) = 1/2; (0,1): 1/2โํ เฏค , because Pr(ํ เฏ = 1) = 1/2; (0,0): ํ เฏค , because the probabilities sum to 1 (so that 1โ(ํ เฏค +1/2โํ เฏค +1/2โํ เฏค ) = ํ เฏค ). We now compute ํ เฏค+เฌต . There are two contributions. First, pairs with (ํ เฏ+เฏค ,ํ เฏ )= (1,1) remain overlapping if the current 1 survives Degrade, giving (1โํ) ํ เฏค . Second, after Degrade, the event (0,1) consists of the original (0,1) pairs and the degraded original (1,1) pairs. Its probability is (1/2โํ เฏค )+ํํ เฏค =1/2โ(1โํ) ํ เฏค . Refill turns these current zeros to 1 with probability ฮฑ. Thus ํ เฏค+เฌต = (1โํ) ํ เฏค +[1/2โ(1โํ) ํ เฏค ] ฮฑ = (1โํ)(1โฮฑ) ํ เฏค +ฮฑ/2. With ฮฑ = ํ/(1+ํ), we have 1โฮฑ = 1/(1+ํ), so the decay parameter becomes ฯ SA := (1โํ)(1โฮฑ) = (1โํ)/(1+ํ), and the constant term is ํ SA := ฮฑ/2 = ํ/[2(1+ํ)]. The recursion can be written as ํ เฏค+เฌต = ฯ SA ํ เฏค +ํ SA , with ํ เฌด = 1/2. Unrolling gives ํ เฏค+เฌต = ฯ SA เฏค+เฌต ํ เฌด +ํ SA (1+ฯ SA +...+ฯ SA เฏค ), where the sum of geometric progression is (1โ ฯ SA เฏค+เฌต )/(1โฯ SA ). With ํ เฌด = 1/2 and ํ SA /(1โฯ SA ) = 1/4, this yields ํ เฏค = 1/4+ฯ SA เฏค /4. Since ํ(ํ,ํ) = 2 ํ(ํ,ํ)/ํท and each component contributes overlap with probability ํ เฏค , for two levels ํ and ํ with separation ฮ := |ํโํ|, we have ํ ฮ = Pr(ํ เฏ = 1,ํ เฏ = 1) = 1/4+(1/ 4)ฯ SA ฮ , hence E[ํ(ํ,ํ)] = ํ SA (ฮ) = 2ํ ฮ = 1/2+(1/2)ฯ SA ฮ . 1.1.2 Properties Parameter range: The update is well-defined for 0 โค ํ โค 1. With ฯ SA = (1โํ)/(1+ํ) from the recursion above, we have ฯ SA โ [0,1], and the similarity law ํ SA (ฮ) = 1/2+(1/2) ฯ SA ฮ is well defined for all integer ฮ โฅ 0. One-step similarity and distance: For consecutive levels (ฮ = 1), ํ SA (1) = 1/2+(1/2) ฯ SA = 1/2+(1/2) (1โํ)/(1+ํ) = 1/(1+ํ). The normalized Hamming distance between levels at distance ฮ is E[dist Ham (ํฅ เฏ ,ํฅ เฏ )] / ํท = (1โฯ SA ฮ ) / 2, so for consecutive levels (ฮ = 1) this gives E[dist Ham (ํฅ เฏ ,ํฅ เฏ+เฌต )] / ํท = (1โฯ SA )/2 = (1โ(1โํ)/(1+ํ))/2 = ํ/ (1+ํ). 38 Executed and net flips: At ํ = 1/2, Degrade executes ํ/2 flips (1โ0) in expectation and Refill executes another ํ/2 flips (0โ1), so the expected number of executed flips per component per level transition is E[ํ exec ] = ํ. Some components flip twice in one step (1โ0 in Degrade, then 0โ1 in Refill). For ํ = 1/2 the double-flip probability per component is Pr(double) = ํ เฌถ / (2(1+ํ)). Each double-flip event contributes two executed flips but zero net flips, so E[ํ exec ] = Pr(net flip)+2Pr(double). With E[ํ exec ] = ํ and Pr(double) = ํ เฌถ /(2(1+ํ)), this gives Pr(net flip) = ํโํ เฌถ /(1+ํ) = ํ/(1+ํ) which agrees with the expression obtained from the distance formula above. 1.2 SingleโCommit 1.2.1 Derivation of Mean Between-Level Similarity (SingleโCommit) It is convenient to recode components as โ1,+1. Define ํ เฏค โ โ1,+1 by ํ เฏค = 2 ํ เฏค โ1, so ํ เฏค = 1 corresponds to ํ เฏค = +1 and ํ เฏค = 0 corresponds to ํ เฏค = โ1, and ํ เฏค เฌถ = 1. Under the SC update, each component flips with probability ํ, so ํ เฏค+เฌต = ํ เฏค ํ เฏค , where ํ เฏค โ โ1,+1 is independent of ํ เฏค , and ํ เฏค s are independent across level transitions, with Pr(ํ เฏค = โ1) = ํ and Pr(ํ เฏค = +1) = 1โํ. Then E[ํ เฏค ] = (1โํ)โํ = 1โ2ํ and Eเตฃํ เฏค ํ เฏคเฌพเฌต เตง=Eเตฃํ เฏค เฌถ ํ เฏค เตง = Eเตฃํ เฏค เตง=1โ2ํ because ํ เฏค เฌถ = 1. For two levels ํ and ํ with separation ฮ := |ํโํ|, iterating the update over ฮ transitions gives E[ํ เฏ ํ เฏ ] = (1โ2ํ) ฮ . Relating this to the overlap of binary vectors, note that since Pr(ํ เฏ = 1)= Pr(ํ เฏ = 1)=1/2, we have E[ํ เฏ ํ เฏ ] = 4 Pr(ํ เฏ = 1,ํ เฏ = 1)โ1, Pr(ํ เฏ = 1,ํ เฏ = 1)= (1+(1โ2ํ) ฮ )/4. Using ํ(ํ,ํ) = 2 ํ(ํ,ํ)/ํท at ํ = 1/2 and the fact that each component contributes overlap with probability Pr(ํ เฏ = 1,ํ เฏ = 1), the induced mean similarity is E[ํ(ํ,ํ)] = ํ SC (ฮ) = 1/2+(1/2) (1โ2ํ) ฮ . 1.2.2 Properties Parameter range: The update is well-defined for 0 โค ํ โค 1. With ฯ SC := 1โ2ํ we have ฯ SC โ [โ1,1], and the similarity law ํ SC (ฮ) = 1/2+(1/2) ฯ SC ฮ is well defined for all integer ฮ โฅ 0. For many applications we restrict to 0 โค ํ โค 1/2 so that ฯ SC โ [0,1] and the similarity decays monotonically with ฮ. One-step similarity and distance. For ฮ = 1, ํ SC (1) = 1/2+(1/2) ฯ SC = 1/2+(1/2) (1โ 2ํ) = 1โํ. The normalized Hamming distance follows from the component-wise XOR identity ํฅ เฏ โ ํฅ เฏ = ํฅ เฏ +ํฅ เฏ โ2(ํฅ เฏ โง ํฅ เฏ ). At ํ = 1/2 this gives E[dist Ham (ํฅ เฏ ,ํฅ เฏ )] / ํท = 1โ E[sim เญขเญญเญฒ (ํฅ เฏ ,ํฅ เฏ )]/(ํท/2) = (1โฯ SC ฮ )/2. For consecutive levels (ฮ = 1) this gives E[dist Ham (ํฅ เฏ ,ํฅ เฏ+เฌต )] / ํท = ํ. Executed versus net flips. Each component flips with probability ํ and never flips twice within the same step, so executed and net flip probabilities coincide and equal ํ per component per step (or ํํท per vector per step). 39 1.3 Comparison of SubtractโAdd and SingleโCommit At ํ = 1/2 the SC and SA updates have ฯ SC = 1โ2 ํ and ฯ SA = (1โํ)/(1+ํ). At ํ = 1/2 both SC and SA execute ํํท flips per step in expectation, so comparing their decay factors ฯ at the same ํ compares the schemes at equal expected executed-flip cost. For 0 < ํ โค 1/2, we have 1โ2 ํ < (1โํ)/(1+ํ), so SC decorrelates faster than SA at this equal-cost calibration. Let ํข denote the net flip probability per component per level transition, equivalently ํข = E[dist Ham (ํฅ เฏ ,ํฅ เฏ+เฌต )] / ํท. If the comparison is made at fixed ํข, then SA has ํข = ํ/(1+ํ) and hence ํ = ํข/(1โํข), whereas for SC at ํ = 1/2 the net flip probability equals the flip probability ํ itself, so setting ํ = ํข parameterizes SC directly by ํข. Under this fixed-net-flip calibration, both updates have decay ฯ = 1โ2 ํข and similarity ํ(ฮ) = 1/2+(1/2) (1โ2 ํข) ฮ ; in particular, ํ(1)=1โํข. However, SA requires extra executed flips to achieve the same net ํข, because components can flip twice within one DegradeโRefill transition. In expectation, SC executes ํขํท flips vs ํทํข/ ( 1โํข ) for SA. Feasibility: At ํ = 1/2, in this comparison we restrict SC to 0 โค ํ โค 1/2 (so that ฯ SC โ [0,1] and the similarity decays monotonically), while SA permits 0 โค ํ โค 1 (ฯ SA โ [0,1]). For SC, ํ = 1/2 gives ฯ = 0 and ํ(ฮ)=1/2 for all ฮ โฅ 1. For SA, ํ = 1 gives similarity 1/2 and ฯ = 0. Comparison with โscatter codeโ (Smith & Stanford, 1990): For one component under the symmetric update with per-step flip probability ํ = 1/ํท, the number of flips over ํ steps is Binomial(ํ,1/ํท). The component differs from its start iff the flip count is odd, which occurs with probability Pr(odd) = (1โ(1โ2/ํท) เฏค )/2. Hence E(dist Ham )/ํท = (1โฯ |เฏเฌฟเฏ| )/2 with ฯ = 1โ2ํ = 1โ2/ํท and |ํโํ| = ํ. Useful limiting regimes: Small ํ โช ํท: (1โ2/ํท) เฏค โ 1โ2ํ/ํท, so E[dist Ham ] โ ํ. For ํ โผ ํท: (1โ2/ํท) เฏค โ ํ เฌฟเฌถเฏค/เฎฝ , so E[dist Ham ]/ํท โ (1โํ เฌฟเฌถเฏค/เฎฝ )/2 and E[dist Ham ] โ (ํท/2)(1โํ เฌฟเฌถเฏค/เฎฝ ). As ํ โ โ, E[dist Ham ]โํท/2. 40 1.4 Markov Chain and Eigenvalue Perspective Above, we derived expected similarity for SA and SC directly from explicit flip and overlap recursions. Here we give a complementary Markov-chain perspective on the same result: for each exponential-family update, the corresponding decay parameter ฯ is the nontrivial eigenvalue of an associated 2ร2 single-component Markov kernel. This viewpoint shows how the same decay factor obtained from the flip/overlap recursions also arises from standard spectral facts for finite Markov chains (see, e.g., (Diaconis & Stroock, 1991), (Fill, 1991), (Diaconis & Saloff-Coste, 1993), (Diaconis, 2009)). 1.4.1 Single-Component Kernels and Eigenvalues at ํ = 1/2 Consider a single component ํ เฏค โ 0,1 evolving across levels as a level-homogeneous two- state Markov chain (same one-component transition rule at every level transition ํโํ+1). The update is specified by a 2ร2 transition kernel with elements ํพ(ํ,ํ) = Pr (ํ เฏค = ํ โ ํ เฏค+เฌต = ํ): ํพ = [[Pr(0โ0),Pr(0โ1)],[Pr(1โ0),Pr(1โ1)]]. Rows are โfromโ states (before the arrow), columns are โtoโ states (after the arrow); row ํ gives the transition probabilities out of state ํ, and each row sums to 1. Let ฯ เฏค denote the probability mass function (pmf) of ํ เฏค , represented as a row vector ฯ เฏค := (Pr(ํ เฏค = 0),Pr(ํ เฏค = 1)). Then the evolution is ฯ เฏค+เฌต = ฯ เฏค ํพ. Now specialize to ํ = 1/2, i.e., Pr(ํ เฏค = 1) = 1/2 for all ํ. This holds if we start from ฯ เฌด = (1/2,1/2) and choose parameters so that ฯ * = (1/2,1/2) is stationary for ํพ. This requires Pr(0โ1) = Pr(1โ0); denote this common flip probability by ฮธ. Then ํพ takes the symmetric โequal-flipโ form ํพ(ฮธ) = [[1โฮธ,ฮธ], [ฮธ,1โฮธ]], 0 โค ฮธ โค 1. To connect this to overlap/similarity, recode 0,1 components to the centered sign variable ํ เฏค = 2 ํ เฏค โ1 โ โ1,+1. Under ฯ * = (1/2,1/2) one has E[ํ เฏค ] = 0. The eigenvalues of ํพ(ฮธ) are ฮป เฌต and ฮป เฌถ . Since each row sums to 1, ฮป เฌต = 1. While ฮป เฌถ = 1โ2ฮธ controls correlation decay: E[ํ เฏ ํ เฏ+ฮ ] = ฮป เฌถ ฮ . In our notation ฯ := ฮป เฌถ and Pr(ํ เฏ = 1,ํ เฏ = 1) = (1+E[ํ เฏ ํ เฏ ]) / 4 = (1+ฯ ฮ ) / 4. Summing over components and using ํ(ํ,ํ) = 2ยทํ(ํ,ํ)/ํท at ํ = 1/2 yields the mean similarity law E[ํ(ํ,ํ)] = 1/2+(1/2)ยทฯ ฮ corresponding to the exponential target law ํ(ฮ) in section 4. For the SC scheme at ํ = 1/2, we have ฮธ = ํ and ฯ SC = 1โ2 ํ, in agreement with section 4.2. For SA at ํ = 1/2, one full level transition is the composition of two one- component substeps: Degrade flips 1โ0 (0 stays 0) with probability ํ, Refill then flips 0โ1 (1 stays 1) with probability ฮฑ chosen so that ฯ * = (1/2,1/2) is stationary for the composed transition. At ํ = 1/2, stationarity requires Pr(0โ1) = Pr(1โ0). For the composed SA step, these probabilities are ฮฑ and ํ(1โฮฑ), respectively; hence ฮฑ = ํ(1โฮฑ), so ฮฑ = ํ/(1+ํ). The resulting one-component transition probabilities for the composed SA step are Pr(0โ0) = 1โฮฑ, Pr(0โ1) = ฮฑ, Pr(1โ0) = ํ (1โฮฑ), Pr(1โ1) = 41 (1โํ)+ํ ฮฑ, so ํพ SA = [[1โฮฑ,ฮฑ],[ํ (1โฮฑ),(1โํ)+ํ ฮฑ]]. Substituting ฮฑ = ํ/(1+ํ) gives ํพ SA = [[1/(1+ํ),ํ/(1+ํ)], [ํ/(1+ํ),1/(1+ํ)]]. This matrix has eigenvalues ฮป เฌต = 1, ฮป เฌถ = (1โํ)/(1+ํ) = ฯ SA , matching section 4.2. 1.4.2 From One Component to ํท Components For SC and SA with independently updated components, the full chain on 0,1 เฎฝ is the ํท-fold product of the one-component chain (ํพ SC or ํพ SA ); consequently, the ํท-dimensional eigenvalues are products of the one-component eigenvalues. The overlap ํ(ํ,ํ) = sim dot (ํฅ เฏ ,ํฅ เฏ ) is the sum of ํท component-wise overlaps. Linearity of expectation gives E[ํ(ํ,ํ)] = ํท Pr(ํ เฏ (ํ) = 1,ํ เฏ (ํ) = 1). Since Pr(ํ เฏ (ํ) = 1, ํ เฏ (ํ) = 1) = (1+ฯ ฮ )/4, we obtain E[ํ(ํ,ํ)] = 1/2+(1/2)ฯ ฮ . Thus, both SC and SA follow ํ(ฮ) = 1/2+(1/2) ฯ ฮ , with ฯ SC = 1โ2 ํ for SC and ฯ SA = (1โํ)/(1+ํ) for SA. 1.4.3 Derandomization Variants For Baseline, the component-wise SC and SA update schemes are treated above. The fixed- count SC variants of section 4.3, including Fixed-F, Fixed-FpD and Fixed-kpD (equal-swap), define Markov chains on 0,1 เฎฝ , but they are not product chains (i.e., the ํท components are not updated independently at each step). Each step flips a constrained number of components (and, for equal-swap, preserves |ํฅ เฏค |), which couples components within a step. Nevertheless, for each fixed component, the marginal flip probability conditional on its current value is ํ. Hence the marginal single-component transition probabilities satisfy Pr(0โ1) = Pr(1โ0) = ํ and the induced single-component kernel is ํพ(ํ) = [[1โํ,ํ],[ํ,1โํ]] with nontrivial eigenvalue ฯ = 1โ2ํ. Although components are coupled within a step, this coupling affects their joint behavior (and thus fluctuations), but it does not change the one-step transition probabilities of a single component; therefore, the mean overlap/similarity still uses the same ฯ. Consequently, in the ํ = 1/2 setting the fixed-count SC variants share the same induced mean similarity law E[ํ(ํ,ํ)] = 1/2+(1/2)ฯ ฮ , while they differ in finite-ํท fluctuation properties because the per-step flips are constrained rather than independent. 1.4.4 Related Markov-Chain Literature and Scope Our sequence of derandomization variants begins with the Baseline variants. Baseline SC (component-wise random flips) and Baseline SA (component-wise Degrade-Refill) both induce, at the component level, a two-state Markov kernel applied independently across components. Consequently, the full ํท-dimensional evolution (up to the chosen initial law) is a product chain of identical two-state component chains. In this setting, overlap/similarity with a fixed anchor reduces to a count statistic: how many components are 1 both in the anchor and in the level reached after ฮ steps. When the component kernel is symmetric/balanced, this count process is closely related to classical Ehrenfest-type chains; general cutoff/mixing results for Ehrenfest chains and product chains (e.g., (Chen et al., 2012), (Chen & Kumagai, 2018)) can therefore serve as optional background if one wishes to discuss worst-case convergence behavior of these 42 baselines. For fixed-count SC derandomization variants, the evolution coincides with classical random walks on discrete state spaces. In the Fixed-F setting (flip exactly ํน components per level), the evolution is a random walk on the ํท-dimensional hypercube. Related asymptotic and spectral analyses include (Diaconis et al., 1990) for single-bit flips and (Nestoridi, 2017) for fixed-count walks. In the Fixed-kpD / equal-swap setting (swap exactly ํ 1โs with ํ 0โs per level), the evolution is a ํ-swap BernoulliโLaplace urn model on the constant Hamming- weight state space of ํท-bit vectors with ํท/2 ones. Equivalently, it is a ํ-swap walk on the Johnson scheme, with the ํ = 1 case corresponding to the standard random walk on the Johnson graph. This connects our equal-swap dynamics to the classical ํ = 1 Bernoulliโ Laplace analysis of (Diaconis & Shahshahani, 1987) and (Donnelly et al., 1994), and to later ํ-swap regimes such as ํ = ํ(ํท) and ํ = ฮ(D) in (Eskenazis & Nestoridi, 2020) and (Alameda et al., 2024). This is consistent with our one-component viewpoint: these classical analyses diagonalize the full transition operator, which has many eigenvalues. Our mean- similarity calculation uses only the eigenvalue associated with the overlap; this eigenvalue corresponds to the decay factor ฯ. The cited cutoff/mixing literature for product/Ehrenfest chains (baseline) or for hypercube/BernoulliโLaplace walks (fixed-count SC derandomizations) primarily targets worst-case convergence to stationarity in global metrics (total variation or separation) and often identifies sharp transition windows (โcutoffโ), typically as a function of an adversarial initial configuration. Our focus is different: we analyze average-case similarity dynamics induced by encoding (mean similarity profile and variance/RMSE), typically from randomly generated anchors, or from anchors produced by the same codebook-generation process, rather than from adversarial worst-case starts. Consequently, exponential mean similarity profiles do not conflict with cutoff phenomena: cutoff is a global statement about the full configuration distribution, while our profiles track a low-dimensional observable (overlap/similarity) governed by low-order spectral structure (the decay factor ฯ), which can relax smoothly even when worst-case distance to stationarity remains large. 1.4.5 Summary A one-component two-state 2ร2 Markov kernel matrix with transition probabilities ํ= Pr(0โ1) and โ=Pr(1โ0) has the second (nontrivial) eigenvalue 1โํโโ. The target density ํ enters through the stationary-balance condition (1โํ)ํ=ํโ. In this paper we specialize to ํ=1/2. For both the SC kernel and the composed one-step SA kernel, after choosing the SA Refill probability to preserve density 1/2, the off-diagonal probabilities are equal: ํ=โ= ํ and the nontrivial eigenvalue equals the one-step decay parameter ฯ step used in section 6.1.1. For component-wise SC/SA, this eigenvalue is ฯ derived from the one-step similarity recursion, with ฯ เฏเฎผ = 1โ2ํ and ฯ เฏเฎบ = (1โํ)/(1+ํ). For fixed-count and equal-swap SC variants, component selections are coupled within a step, but each individual component still 43 has flip probability r; therefore, the mean overlap/similarity evolves with the same decay factor ฯ เฏเฎผ = 1โ2ํ, while the coupling affects finite-D variance. Thus, the Markov-kernel viewpoint reinterprets the same decay parameter already used in sections 4.2 and 6.1.1. 44 2 Supplementary Note 2: Linear Similarity Family Mean Laws and Finite-Capacity Effects 2.1 Proof of Lemma 5.1 Proof. Step 1 (pool depletion โ agreement probability). This step uses only the w.o.r. requirement and the independence of ํฝ from the generator randomness. Under w.o.r. dynamics, the component at index ํฝ differs between levels ํ and ํ if and only if ํฝ โ ํ เฏ and ํฝ โ ํ เฏ , since ํ เฏ โ ํ เฏ (the pool is shrinking in ํ). Hence Pr(ํฅ เฏ (ํฝ) โ ํฅ เฏ (ํฝ)) = Pr(ํฝ โ ํ เฏ )โPr(ํฝ โ ํ เฏ ). Conditioning on ํ เฏค and using that ํฝ is uniform and independent gives Pr(ํฝ โ ํ เฏค | ํ เฏค ) = |ํ เฏค |/ํท, hence Pr(ํฝ โ ํ เฏค ) = E[|ํ เฏค |]/ํท. Therefore Pr(ํฅ เฏ (ํฝ) โ ํฅ เฏ (ํฝ)) = (E[|ํ เฏ |]โE[|ํ เฏ |])/ ํท and Pr(ํฅ เฏ (ํฝ) = ํฅ เฏ (ํฝ)) = 1โ(E[|ํ เฏ |]โE[|ํ เฏ |])/ํท. This proves (i). Step 2 (overlap-normalized similarity โ agreement probability at ํ = 1/2). This step does not use the w.o.r. requirement; it uses ํ = 1/2 complement-invariant initialization, and value-independent selection. By definition of ํ(ํ,ํ) and uniform ํฝ, E[ํ(ํ,ํ)] = ํท Pr(ํฅ เฏ (ํฝ) = 1,ํฅ เฏ (ํฝ) = 1), hence E[ํ(ํ,ํ)] = (2/ ํท) E[ํ(ํ,ํ)] = 2Pr(ํฅ เฏ (ํฝ) = 1,ํฅ เฏ (ํฝ) = 1). For any fixed ํฎ, ํฆ โ 0,1 เฎฝ : 1โ(ํฎ โ ํฆ) = (1โํฎ) โ ํฆ. Consider ํฆ ( เฏค ) = ํฆ เฌด โ ... โ ํฆ เฏคเฌฟเฌต . If ํฑ เฌด = ํฎ and ํฑ เฏค = ํฑ เฌด โ ํฆ (เฏค) , then 1โํฑ เฏค = (1โํฑ เฌด ) โ ํฆ (เฏค) . Therefore, with the same masks, replacing any fixed ํฑ เฌด by its component-wise complement 1โํฑ เฌด complements every level ํ โค ํ: ํฑ เฏค โ 1โํฑ เฏค . In particular, (ํฅ เฏ (ํฝ), ํฅ เฏ (ํฝ)) maps to (1โ ํฅ เฏ (ํฝ),1โํฅ เฏ (ํฝ)). By Assumption (A), ํฑ เฌด and 1โํฑ เฌด have the same distribution. Let ํ denote the entire realized mask sequence up to level ํ. By Assumption (B), the distribution of ํ is unchanged when ํฑ เฌด is replaced by 1โํฑ เฌด . Together, these imply that the joint pairs (ํฑ เฌด , ํ) and (1โํฑ เฌด , ํ) have the same distribution. Condition on ํ: Since the mapping ํฅ เฌด โ 1โํฅ เฌด deterministically maps (ํฅ เฏ (ํฝ), ํฅ เฏ (ํฝ)) to (1โํฅ เฏ (ํฝ),1โํฅ เฏ (ํฝ)) under the same ํ, the conditional distribution of (ํฅ เฏ (ํฝ), ํฅ เฏ (ํฝ)) given ํ is invariant under complementation. Hence, for every realized ํ, Pr(ํฅ เฏ (ํฝ) = 1, ํฅ เฏ (ํฝ) = 1| ํ) = Pr(ํฅ เฏ (ํฝ) = 0,ํฅ เฏ (ํฝ) = 0|ํ). Taking expectations over ํ gives unconditional probabilities: Pr(ํฅ เฏ (ํฝ) = 1,ํฅ เฏ (ํฝ) = 1) = Pr(ํฅ เฏ (ํฝ) = 0,ํฅ เฏ (ํฝ) = 0). Consequently, E [ ํ ( ํ,ํ )] = 2Pr ( ํฅ เฏ ( ํฝ ) = 1,ํฅ เฏ ( ํฝ ) = 1 ) = Pr(ํฅ เฏ (ํฝ) = 1,ํฅ เฏ (ํฝ) = 1)+Pr(ํฅ เฏ (ํฝ) = 0,ํฅ เฏ (ํฝ) = 0) = Pr(ํฅ เฏ (ํฝ) = ํฅ เฏ (ํฝ)). This proves (i). โ 2.2 Random-Count Remaining-Pool Constructions 2.2.1 Proposition 1: Adaptive Thinning on the Remaining Pool 45 For some remaining-pool w.o.r. generator constructions, the selection mechanism can be expressed as adaptive Bernoulli thinning of ํ เฏค , with capacity capping near exhaustion. Let ํน เฏคเฌพเฌต denote the executed flip count in transition ํ โ ํ+1. It is random but capped by the current pool size |ํ เฏค |. Conditional on ํ เฏค with เธซํ เฏค เธซ>0, each component in ํ เฏค is selected independently with inclusion probability min(1,ํน/|ํ เฏค |), where ํน = ํท/ํ is the nominal target flip count per level. If เธซํ เฏค เธซ=0, no component is selected. Thus ํน เฏค+เฌต | ํ เฏค ~ Bin(|ํ เฏค |,min(1,ํน/|ํ เฏค |)), with |ํ เฏค+เฌต | = |ํ เฏค |โํน เฏค+เฌต . Hence E[ํน เฏค+เฌต | ํ เฏค ] = min(ํน,|ํ เฏค |), and taking expectations gives the exact recursion E[|ํ เฏค+เฌต |] = E[|ํ เฏค |]โ E[min(ํน,|ํ เฏค |)] = E[|ํ เฏค |]โํน+E[max(ํนโ|ํ เฏค |,0)]. By Lemma 5.1, the mean similarity between levels ํ and ํ+ฮ is E [ ํ ( ํ,ํ+ฮ )] = 1โ ( E [| ํ เฏ |] โE [| ํ เฏ+ฮ |]) /ํท= 1โฮF/D+(1/ํท)โ เฏค=เฏ เฏเฌพฮเฌฟเฌต E[max(ํนโ|ํ เฏค |,0)]. Thus, deviations of E[ํ(ํ,ํ+ฮ)] from the target law ํ lin (ฮ) arise from these finite-capacity correction terms, which are negligible away from exhaustion and become appreciable as the probability that the remaining pool falls below ํน increases. 2.2.2 Proposition 2: Fixed-Order Proposed-Count Selection with Truncation At transitions ํ โ ํ+1, let ํ เฏคเฌพเฌต be i.i.d. proposed counts with ํ เฏคเฌพเฌต ~ Bin(ํท,1/ํ). The generator proposes ํ เฏคเฌพเฌต flips but executes only min(ํ เฏคเฌพเฌต ,|ํ เฏค |), flipping the next previously unused components along a fixed ordering. Define ํถ เฏค := โ เฏง=เฌต เฏค ํ เฏง ~ Bin(ํทํ,1/ํ), so |ํ เฏค | = D โmin(ํถ เฏค ,ํท)=max(ํทโํถ เฏค ,0) and E[|ํ เฏค |] = E[max(ํทโํถ เฏค ,0)]. By Lemma 5.1, E [ ํ ( ํ,ํ+ฮ )] = 1โ(E [| ํ เฏ |] โE[|ํ เฏ+ฮ |])/ํท=1โฮF/D+(1/D) (E[max(ํถ เฏ+ฮ โํท,0)]โ E[max(ํถ เฏ โํท,0)]). Thus, deviations from ํ lin ( ฮ ) =1โฮF/D arise from the overshoot terms created by the one-sided truncation ํถ เฏค โ min(ํถ เฏค ,ํท). These terms are negligible away from pool exhaustion and become appreciable near the terminal boundary, where they produce the upward terminal bias. 2.2.3 Remark 3: Terminal Bias Scale At ํ = ํ in Proposition 2, |ํ เฏ | = max(ํทโํถ เฏ ,0), so E[|ํ เฏ |]>0 even though ํทโ E[ํถ เฏ ] = 0. By Lemma 5.1, E[ํ(0,ํ)] = E[|ํ เฏ |]/ํท = (1/ํท) E[max(ํทโํถ เฏ ,0)]. Since ํถ เฏ ~ Bin(ํทํ,1/ํ), it has mean ํท and variance ํท(1โ1/ํ). By the de MoivreโLaplace approximation for a binomial with large ํทํ, we have ํทโํถ เฏ โ ํ ~ Norm(0,ํท(1โ1/ํ)). The standard identity E [ max ( ํ,0 )] = ฯ/ ( 2ฯ ) เฌต/เฌถ therefore gives E[ํ(0,ํ)] โ ((1โ1/ํ)/ (2ฯD)) เฌต/เฌถ . Thus, one-sided truncation induces a small positive terminal mean similarity even though ํ lin (ํ) = 0: overshoots are clipped at zero remaining capacity while undershoots leave a positive residual pool. Empirically, fixed-order variants (Proposition 2) show a slightly larger terminal bias than the adaptive Bernoulli-thinning variants (Proposition 1): the proposed per-level counts are i.i.d. and can overshoot the remaining pool near exhaustion, whereas Bernoulli-thinning on ํ เฏค 46 adapts via min(1,ํน/|ํ เฏค |) and empties the remaining pool in the next transition whenever |ํ เฏค | < ํน, since then min(1,ํน/|ํ เฏค |)=1 and therefore ํน เฏค+เฌต = |ํ เฏค |. 2.2.4 Corollary 4: Fixed-Count W.O.R. Constructions Assume that each level transition flips exactly ํน previously unused components, and that the pool is exhausted exactly at level ํ, i.e., ํน = ํท/ํ is an integer. Then |ํ เฏค | = ํทโํํน deterministically. Hence, for any anchor ํ and separation ฮ with ํ+ฮ โค ํ, E[ํ(ํ,ํ+ฮ)] = 1โฮโF/ํท = ํ lin (ฮ). Moreover, dist Ham (ํฑ เฏ ,ํฑ เฏ+ฮ ) = ฮโF, so sim ham = ํ lin (ฮ) exactly. 47 3 Supplementary Note 3: Accuracy of Approximating the Target Similarity Laws This section derives exact finite-dimensional (finite-D) expressions characterizing how closely each generator matches the target law ํ(ฮ). For each similarity family (Exponential, Linear) and each derandomization variant (Baseline, Fixed-pD, Fixed-F, Fixed-FpD, Fixed-kpD), we provide ฮผ th (ํ,ํ), bias th (ํ,ํ) and v th (ํ,ํ). RMSE th is then obtained from these quantities using the paperโs evaluation protocol of section 3.3, and compared to experiments in section 7.2. We start with finite-N properties of empirical error estimates. 3.1 Finite-N Properties of Empirical Error Estimates For each fixed pair (ํ,ํ), ํธ[ฮผ emp (ํ,ํ)]= ฮผ ( ํ,ํ ) , Var(ฮผ emp (ํ,ํ)) = v(ํ,ํ)/ํ, E[MSE emp (ํ,ํ)] = MSE(ํ,ํ). The empirical bias and variance have finite-N corrections. Since bias emp (ํ,ํ) := ฮผ emp (ํ,ํ)โํ(ํ,ํ), we have E[bias emp เฌถ (ํ,ํ)] = bias เฌถ (ํ,ํ)+v(ํ,ํ)/ํ. Since v emp (ํ,ํ) is normalized by 1/ํ, we have E[v emp (ํ,ํ)] = (1โ1/ํ)ยทv(ํ,ํ). Averaging these identities over ํ gives E[BiasRMS emp เฌถ (ํ)] = BiasRMS เฌถ (ํ)+VarRMS เฌถ (ํ)/ ํ, E[VarRMS emp เฌถ (ํ)] = (1โ1/N) VarRMS เฌถ (ํ), E[RMSE emp เฌถ (ํ)]=RMSE เฌถ (ํ). 3.2 Finite-D Accuracy for Exponential Similarity Family We analyze the SC scheme from section 4.2 and its generator constructions from section 4.3. Because ํ(ํ,ํ), bias th (ํ,ํ), and v th (ํ,ํ) are symmetric in (ํ,ํ), we assume ํ โค ํ without loss of generality and write ฮ := ํโํ throughout this section. For the Baseline, Fixed-pD, Fixed-F, Fixed-FpD derandomization variants and their generators, the theory can be expressed in terms of two one-step generator parameters ฯ step and ฮณ step (defined below) that summarize the randomness of a single transition ํ โ ํ+1. Let ํ เฏค โ 1,...,ํท be the flip-index set at transition ํ โ ํ+1, and use the ยฑ1 encoding ํฆ เฏค (ํ) := 2ํฅ เฏค (ํ)โ1, so that ํฅ เฏค (ํ) = (1+ํฆ เฏค (ํ))/2. Define the per-component multiplier ํ เฏค (ํ) โ +1,โ1 by ํ เฏค (ํ) = -1 iff ํ โ ํ เฏค and ํ เฏค (ํ) = +1 otherwise, so ํฆ เฏค+เฌต (ํ) = ํ เฏค (ํ)ยทํฆ เฏค (ํ). (3.1) Under level-homogeneity and exchangeability, the following generator one-step parameters do not depend on ํ, ํ, or the particular pair (ํ,ํ), ํ โ ํ: ฯ step := E[ํ เฏค (ํ)] (mean one-step sign multiplier), ฮณ step := E[ํ เฏค (ํ)ยทํ เฏค (ํ)] for ํ โ ํ (mean product of the two multipliers for two distinct components in the same step). If the mask decisions are independent across components within a step, then ฮณ step = ฯ step เฌถ ; fixed-count selection generally yields ฮณ step โ ฯ step เฌถ . These one-step parameters determine the derived quantities: ฯ step determines the mean 48 similarity profile and hence bias th (ํ,ํ), while (ฯ step ,ฮณ step ) determine v th (ํ,ํ). The target exponential law uses parameter ฯ in ํ exp (ฮ). However, we show that ฯ step = ฯ and therefore bias th (ํ,ํ) = 0. For Fixed-kpD (equal-swap), v th (ํ,ํ) is computed via a dedicated overlap- moment recursion that does not use ฮณ step explicitly. 3.2.1 Common Derivation for Baseline, Fixed-pD, Fixed-F, and Fixed-FpD Mean similarity and bias: Iterate (3.1) across ฮ transitions. Since the masks are sampled independently across steps and their distribution is level-homogeneous, ํฆ เฏ (ํ) = ํฆ เฏ (ํ) โ เฏง = เฏ เฏเฌฟเฌต ํ เฏง (ํ), hence ํฆ เฏ (ํ)ยทํฆ เฏ (ํ) = โ เฏง = เฏ เฏเฌฟเฌต ํ เฏง (ํ), because ํฆ เฏ เฌถ (ํ) = 1. Taking expectation over realizations gives E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = (E[ํ เฏค (ํ)]) ฮ = ฯ step ฮ . (3.2) Component-wise, ํฅ เฏ (ํ)ยทํฅ เฏ (ํ) = (1+ํฆ เฏ (ํ))(1+ํฆ เฏ (ํ))/4 = 1/4+(ํฆ เฏ (ํ)+ํฆ เฏ (ํ))/4+(ํฆ เฏ (ํ)ยทํฆ เฏ (ํ))/4. (3.3) At ํ = 1/2 we have E[ํฆ เฏ (ํ)] = E[ํฆ เฏ (ํ)] = 0, hence E[ํฅ เฏ (ํ)ยทํฅ เฏ (ํ)] = 1/4+(1/ 4)E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = 1/4+(1/4)ฯ step ฮ . Since ํ(ํ,ํ) = โ เฏ (ํฅ เฏ (ํ) ํฅ เฏ (ํ)), exchangeability gives E[ํ(ํ,ํ)] = ํทยทE[ํฅ เฏ (1) ํฅ เฏ (1)], and using ํ(ํ,ํ) = 2 ํ(ํ,ํ)/ํท, we obtain ฮผ th (ํ,ํ) := E[ํ(ํ,ํ)] = 2ยทE[ํฅ เฏ (1) ํฅ เฏ (1)] = 1/2+(1/2)ฯ step ฮ . The corresponding bias is bias th (ํ,ํ) := ฮผ th (ํ,ํ)โํ exp (ฮ). Finite-ํท variance derivation for v th (ํ,ํ): Define ํ เฏ := ํฆ เฏ (ํ)ยทํฆ เฏ (ํ), ํด เฏค := โ เฏ = เฌต เฎฝ ํฆ เฏค (ํ), and ํถ ab := โ เฏ = เฌต เฎฝ ํ เฏ . Summing ํฅ เฏ (ํ) ํฅ เฏ (ํ) over ํ gives the decomposition via (3.3): ํ(ํ,ํ) = โ เฏ = เฌต เฎฝ ํฅ เฏ (ํ) ํฅ เฏ (ํ) = ํท/4+(ํด เฏ +ํด เฏ +ํถ ab )/4, so Var(ํ(ํ,ํ)) = (1/16)ยทVar(ํด เฏ +ํด เฏ +ํถ ab ). At ํ = 1/2, the distribution over realizations of the full sign sequence is invariant under the global sign flip ํฆ โโํฆ for all levels (the initialization is sign-symmetric and the update masks do not depend on current values). Under this flip, ํด เฏ +ํด เฏ changes sign while ํถ ab does not. Therefore Cov(ํด เฏ +ํด เฏ ,ํถ ab ) = 0 and Var(ํ(ํ,ํ)) = (1/16)ยท(Var(ํด เฏ +ํด เฏ )+Var(ํถ ab )). Finally, since ํ(ํ,ํ) = 2ยทํ(ํ,ํ)/ํท for ํ = 1/2, v th (ํ,ํ) := Var(ํ(ํ,ํ)) = 4ยทVar(ํ(ํ,ํ))/ํท เฌถ = (Var(ํด เฏ +ํด เฏ )+Var(ํถ ab )) / (4ยทํท เฌถ ). (3.4) The term Var(ํถ ab ) depends only on ฯ step and ฮณ step . Indeed, for ํ โ ํ, ํ เฏ ํ เฏ = โ เฏง = เฏ เฏเฌฟเฌต (ํ เฏง (ํ)ยทํ เฏง (ํ)), so E[ํ เฏ ํ เฏ ] = ฮณ step ฮ . Using exchangeability of the ํ เฏ , Var(ํถ ab ) = ํทยทVar(ํ เฌต )+ํทยท(ํทโ1)ยทCov(ํ เฌต ,ํ เฌถ ) = ํทยท(E[ํ เฌต เฌถ ]โ(E[ํ เฌต ]) เฌถ )+ํทยท(ํทโ 1)ยท(E[ํ เฌต ํ เฌถ ]โ(E[ํ เฌต ]) เฌถ ). We have ํ เฏ เฌถ = 1, so E[ํ เฌต เฌถ ] = 1, E[ํ เฌต ] = ฯ step ฮ by (3.2) and E[ํ เฌต ํ เฌถ ] = ฮณ step ฮ . Thus 49 Var(ํถ ab ) = ํทยท(1โฯ step เฌถฮ )+ํท(ํทโ1)(ฮณ step ฮ โฯ step เฌถฮ ). (3.5) The remaining term Var(ํด เฏ +ํด เฏ ) depends on the initialization; we evaluate it next. 3.2.2 Bernoulli-Start Derandomization Variants (Baseline, Fixed-F) We have ํฆ เฌด (ํ) i.i.d. Rademacher, so ํด เฌด = โ เฏ = เฌต เฎฝ ํฆ เฌด (ํ) has E[ํด เฌด ] = 0 and Var(ํด เฌด ) = ํท. For any ํ, each component evolves as ํฆ เฏค (ํ) = ํฆ เฌด (ํ) โ เฏง = เฌด เฏคเฌฟเฌต ํ เฏง (ํ). Since the masks are independent of ํฆ เฌด and the update is component-wise sign multiplication, ํฆ เฏค is a component-wise sign-flip of the i.i.d. Rademacher vector ํฆ เฌด . Hence each ํฆ เฏค (ํ) is Rademacher and remains independent across ํ. Therefore E[ํด เฏค ] = 0 and Var(ํด เฏค ) = ํท for all ํ. The cross-level covariance of ํด เฏ and ํด เฏ is also controlled by ฯ step . Indeed, since E[ํด เฏ ] = E[ํด เฏ ] = 0, we have Cov(ํด เฏ ,ํด เฏ ) = E[ํด เฏ ํด เฏ ]โE[ํด เฏ ] E[ํด เฏ ] = E[ํด เฏ ํด เฏ ]. Expanding, Cov(ํด เฏ ,ํด เฏ ) = โ เฏ = เฌต เฎฝ โ เฏ = เฌต เฎฝ E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)]. If ํ โ ํ, ํฆ เฏ (ํ) = ํฆ เฌด (ํ)ยทโ เฏง = เฌด เฏเฌฟเฌต ํ เฏง (ํ) and ํฆ เฏ (ํ) = ํฆ เฌด (ํ)ยทโ เฏง = เฌด เฏเฌฟเฌต ํ เฏง (ํ). Since the masks are independent of ํฆ เฌด and E[ํฆ เฌด (ํ)ยทํฆ เฌด (ํ)] = 0 for ํ โ ํ under the Bernoulli start, we get E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = 0. If ํ = ํ, (3.2) gives E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = ฯ step ฮ . Summing the ํท diagonal terms gives Cov(ํด เฏ ,ํด เฏ ) = ํทยทฯ step ฮ . Then, Var(ํด เฏ +ํด เฏ ) = Var(ํด เฏ )+Var(ํด เฏ )+2ยทCov(ํด เฏ ,ํด เฏ ) = 2ํท+2ํทยทฯ step ฮ . Substituting this and (3.5) into (3.4) yields v th (ํ,ํ) for the Bernoulli-start generators once (ฯ step ,ฮณ step ) are specified. Baseline (Bernoulli start): For a single component ํ, ํ เฏค (ํ) = +1 with probability 1โํ and ํ เฏค (ํ) = โ1 with probability ํ, so ฯ step = E[ํ เฏค (ํ)] = (1โํ)ยท(+1)+ํยท(โ1) = 1โ2ํ. We obtain ฯ step = ฯ, therefore ฮผ th (ํ,ํ) = ํ exp (ฮ) and bias th (ํ,ํ) = 0. For ํ โ ํ, Baseline mask entries are independent across components, so ฮณ step = E[ํ เฏค (ํ)ยทํ เฏค (ํ)] = E[ํ เฏค (ํ)]ยทE[ํ เฏค (ํ)] = ฯ step เฌถ . To obtain v th (ํ,ํ), we use (3.4) with ฯ step and ฮณ step = ฯ step เฌถ to evaluate Var(ํถ ab ) and Var(ํด เฏ +ํด เฏ ). Fixed-F (Bernoulli start): The mask flips exactly ํน of ํท components uniformly. Hence for any ํ, Pr(ํ เฏค (ํ) = โ1) = ํน/ํท and Pr(ํ เฏค (ํ) = +1) = 1โํน/ํท, so ฯ step = E[ํ เฏค (ํ)] = (1โ ํน/ํท)โ(ํน/ํท) = 1โ2ํน/ํท. For ํ โ ํ, ํ เฏค (ํ)ยทํ เฏค (ํ) = โ1 iff exactly one of ํ,ํ is flipped, otherwise ํ เฏค (ํ)ยทํ เฏค (ํ) = 1. Therefore E[ํ เฏค (ํ) ํ เฏค (ํ)] = (+1)ยทPr(ํ เฏค (ํ)ยทํ เฏค (ํ) = 1)+(โ1)ยทPr(ํ เฏค (ํ)ยทํ เฏค (ํ) = โ1) = 1โ2ยทPr(ํ เฏค (ํ)ยทํ เฏค (ํ) = โ 1). Compute Pr(ํ เฏค (ํ)ยทํ เฏค (ํ) = โ1). This occurs iff exactly one of ํ,ํ is flipped. Pr(ํ flipped, ํ not) = Pr(ํ flipped)ยทPr(ํ not | ํ flipped) = (ํน/ํท)ยท((ํทโํน)/(ํทโ1)). By symmetry, Pr(ํ not,ํ flipped) is the same. Hence Pr(ํ เฏค (ํ)ยทํ เฏค (ํ) = โ1) = 2ยท(ํน/ํท)ยท((ํทโ ํน)/(ํทโ1)) = 2ํน(ํทโํน)/(ํท(ํทโ1)). Thus ฮณ step = 1โ4ํน(ํทโํน)/(ํท(ํทโ1)). Now, we specialize ฮผ th (ํ,ํ) and bias th (ํ,ํ). With ํน = ํํท, we get ฯ step = 1โ 2ํน/ํท = 1โ2ํ = ฯ, hence ฮผ th (ํ,ํ) = ํ exp (ฮ) and bias th (ํ,ํ) = 0. To obtain v th (ํ,ํ), we use (3.4) with these ฯ step and ฮณ step to evaluate Var(ํถ ab ) and the Bernoulli-start case for Var(ํด เฏ +ํด เฏ ). 50 3.2.3 Constant Hamming-Weight Initialization Variants (Fixed-pD, Fixed-FpD) Here ํฅ เฌด has exactly ํท/2 ones, so E[ํฆ เฌด (ํ)] = 0. For ํ โ ํ we compute E[ํฆ เฌด (ํ)ยทํฆ เฌด (ํ)] as follows: 0 = E[(โ เฏ ํฆ เฌด (ํ)) เฌถ ] = E[โ เฏ (ํฆ เฌด (ํ)) เฌถ +โ เฏโ เฏ ํฆ เฌด (ํ) ํฆ เฌด (ํ)] = ํท+ํท(ํทโ1)ยทE[ํฆ เฌด (ํ) ํฆ เฌด (ํ)], hence E[ํฆ เฌด (ํ) ํฆ เฌด (ํ)] = โ1/(ํทโ1) for ํ โ ํ. Same-level correlations: For ํ โ ํ, using ํฆ เฏค (ํ) = ํฆ เฌด (ํ) โ เฏง = เฌด เฏคเฌฟเฌต ํ เฏง (ํ) and independence across level transitions, E[ํฆ เฏค (ํ)ํฆ เฏค (ํ)] = (E[ํ เฏค (ํ)ํ เฏค (ํ)]) เฏค E[ํฆ เฌด (ํ)ํฆ เฌด (ํ)] = โฮณ step เฏค /(ํทโ1). (3.6) Since E[ํฆ เฏค (ํ)] = 0, we have Cov(ํฆ เฏค (ํ),ํฆ เฏค (ํ)) = E[ํฆ เฏค (ํ) ํฆ เฏค (ํ)] for ํ โ ํ and Var(ํฆ เฏค (ํ)) = 1. Therefore Var(ํด เฏค ) = Var(โ เฏ = เฌต เฎฝ ํฆ เฏค (ํ)) = โ เฏ Var(ํฆ เฏค (ํ))+โ เฏโ เฏ Cov(ํฆ เฏค (ํ),ํฆ เฏค (ํ)) = ํท+ํท(ํทโ1)ยท(โฮณ step เฏค /(ํทโ1)) = ํทยท(1โฮณ step เฏค ). Cross-level covariance: Since E[ํด เฏ ] = E[ํด เฏ ] = 0, we have Cov(ํด เฏ ,ํด เฏ ) = E[ํด เฏ ํด เฏ ] = โ เฏ = เฌต เฎฝ โ เฏ = เฌต เฎฝ E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)]. If ํ = ํ, (3.2) gives E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = ฯ step ฮ . If ํ โ ํ, write ํฆ เฏ (ํ) = ํฆ เฏ (ํ) โ เฏง = เฏ เฏเฌฟเฌต ํ เฏง (ํ). The masks in level transitions ํก = ํ,...,ํโ1 are independent of the past, hence E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = E[โ เฏง = เฏ เฏเฌฟเฌต ํ เฏง (ํ)] E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = ฯ step ฮ E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)]. Using (3.6) at ํ = ํ gives E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = โฮณ step เฏ /(ํทโ1), so E[ํฆ เฏ (ํ)ยทํฆ เฏ (ํ)] = โฯ step ฮ ยทฮณ step เฏ /(ํทโ1) for ํ โ ํ. Therefore Cov(ํด เฏ ,ํด เฏ ) = ํทยทฯ step ฮ ยท(1โฮณ step เฏ ), hence Var(ํด เฏ +ํด เฏ ) = ํท(2โฮณ step เฏ โฮณ step เฏ +2ฯ step ฮ (1โฮณ step เฏ )). (3.7) Fixed-pD: The per-step mask distribution is the same as in Baseline, hence ฯ step = 1โ2ํ = ฯ and ฮณ step = ฯ step เฌถ . Because ฯ step = ฯ, we get bias th (ํ,ํ) = 0. The v th (ํ,ํ) is obtained by evaluating (3.4) with these (ฯ step ,ฮณ step ) and the constant Hamming-weight start case for Var(ํด เฏ +ํด เฏ ) (3.7). Fixed-FpD: The per-step mask distribution is the same fixed-count mask as in Fixed-ํน, hence ฯ step = 1โ2ํน/ํท and ฮณ step = 1โ4ยทํน(ํทโํน)/(ํท(ํทโ1)). We have ฯ step = 1โ2ํน/ ํท = 1โ2ํ = ฯ, hence bias th (ํ,ํ) = 0. The v th (ํ,ํ) is obtained by evaluating (3.4) with these (ฯ step ,ฮณ step ) and the constant Hamming-weight-start expression (3.7) for Var(ํด เฏ +ํด เฏ ). Table: Variance summary (Exponential family, ํ = 1/2). Variance uses the common template v th ( ํ,ํ ) = เตซVar ( ํด เฏ +ํด เฏ ) +Var ( ํถ ab ) เตฏ/ ( 4 ํท 2 ) with Var ( ํถ ab ) given by (6.2), whereas Var ( ํด เฏ +ํด เฏ ) differs between Bernoulli and constant Hamming-weight initializations. All terms are instantiated using the ฯ step and ฮณ step listed in the table. Baseline Fixed-pD Fixed-F Fixed-FpD Start Bernoulli(1/2) |ํฅ เฌด | = ํท/2 Bernoulli(1/2) |ํฅ เฌด | = ํท/2 Mask per step Bernoulli(ํ) Bernoulli(ํ) exactly ํน = ํํท exactly ํน = ํํท 51 Baseline Fixed-pD Fixed-F Fixed-FpD ฯ step 1โ2ํ 1โ2ํ 1โ2ํน/ํท 1โ2ํน/ํท ฮณ step ฯ step เฌถ ฯ step เฌถ 1โ4ํน(ํทโํน)/ (ํท(ํทโ1)) 1โ4ํน(ํทโํน)/ (ํท(ํทโ1)) Var(ํด เฏ +ํด เฏ ) (6.3) (6.4) (6.3) (6.4) 3.2.4 Constant Hamming-Weight Initialization and Fixed Swap Count (Fixed-kpD) Mean and bias: Fix anchor level ํ. For ํ = 0,1,...,ํโํ consider the overlap ํ(ํ,ํ+ํ) (so at ํ = ํโํ we have ํ+ํ = ํ). For one equal-swap step (from ํ to ํ+1), condition on ํ(ํ,ํ+ํ) = ํ. At both levels ํ and ํ+ํ there are exactly ํท/2 ones. Among the ํท/2 components that are 1 at level ํ, exactly ํ are still 1 at level ํ+ํ, and the remaining ํท/2โ ํ are 0 at level ํ+ํ. One equal-swap step transforms ํฅ เฏ+เฏ into ํฅ เฏ+เฏ+เฌต by flipping ํ ones to zeros and ํ zeros to ones. Define: ํ = # of selected โ1โ0โ flips that fall inside the level-ํ ones; ํ | ํ ~ Hypergeometric(ํท/2,ํ,ํ); ํ = # of selected โ0โ1โ flips that fall inside the level-ํ ones; ํ | ํ ~ Hypergeometric(ํท/2,ํท/2โํ,ํ). Given ํ, the ํ selected ones and the ํ selected zeros are sampled independently from the disjoint sets. Hence ํ and ํ are independent given ํ, and ํ(ํ,ํ+ํ+1) = ํโํ+ํ. Taking conditional expectations E step over the within-step randomness in this one equal-swap transition (i.e., over the random choice of the ํ ones and ํ zeros selected to flip at level ํ+ํ), E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ) = ํ] = ํโE step [ํ | ํ]+E step [ํ | ํ], where E step [ํ | ํ] = ํยท(ํ/(ํท/2)) and E step [ํ | ํ] = ํยท((ํท/2โํ)/(ํท/2)). Therefore E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ) = ํ] = (1โ4ํ/ํท)ยทํ+ํ = ฯ step ยทํ+ํ, where ฯ step = 1โ4ํ/ํท. Hence ํ = (ํท/4)ยท(1โฯ step ), which is used in final formulas. Applying the law of total expectation to the random variable ํ(ํ,ํ+ํ) (with outer E[ยท] over generator realizations and E step over the within-transition selection randomness) gives: E[ํ(ํ,ํ+ํ+1)] = E[E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ)]] = ฯ step ยทE[ํ(ํ,ํ+ํ)]+ํ, with base case ํ(ํ,ํ) = ํท/2. This yields the closed form E[ํ(ํ,ํ+ํ)] = ํท/4+(ํท/4)ยทฯ step เฏ . Therefore, ฮผ th (ํ,ํ) := E[ํ(ํ,ํ)] = 2ยทE[ํ(ํ,ํ)]/ํท = 1/2+(1/2)ยทฯ step ฮ . With ํ := ํํท/2, we have ฯ step = 1โ4ํ/ํท = 1โ2ํ = ฯ, hence bias th (ํ,ํ) = ฮผ th (ํ,ํ)โํ exp (ฮ) = 0. Finite-D variance v th (ํ,ํ): Since Var(ํ(ํ,ํ)) = E[ํ เฌถ (ํ,ํ)]โ(E[ํ(ํ,ํ)]) เฌถ , we use the closed form for E[ํ(ํ,ํ+ํ)] above and compute E[ํ เฌถ (ํ,ํ+ํ)] by iterating the one-step update for ํ = 0,...,ํโํโ1; this yields E[ํ เฌถ (ํ,ํ+(ํโํ))] = E[ํ เฌถ (ํ,ํ)] and hence Var(ํ(ํ,ํ)). Then v th (ํ,ํ) := 4Var(ํ(ํ,ํ))/ํท เฌถ . (3.8) We already have E [ ํ ( ํ,ํ+ํ )] in closed form above; we obtain E [ ํ เฌถ ( ํ,ํ+ํ )] by a one-step recursion. Start from the conditional identity (for a single step, conditional on ํ ( ํ,ํ+ํ ) ): 52 E step [ ํ เฌถ ( ํ,ํ+ํ+1 ) | ํ ( ํ,ํ+ํ )] = Var step เตซํ ( ํ,ํ+ํ+1 ) เธซ ํ ( ํ,ํ+ํ ) เตฏ+เตซE step [ ํ ( ํ,ํ+ํ+1 ) | ํ ( ํ,ํ+ํ )] เตฏ เฌถ . Taking E of both sides and using the law of total expectation gives E[ํ เฌถ (ํ,ํ+ํ+1)] = E[E step [ํ เฌถ (ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ)]] = E[Var step (ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ))]+E[(E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ)]) เฌถ ]. For the first term, use the hypergeometric variance. Let ํ := ((ํท/2)โํ)/((ํท/2)โ 1). Then Var step (ํ | ํ) = ํยท(ํ/(ํท/2))ยท(1โํ/(ํท/2))ยทํ, and Var step (ํ | ํ) has the same value, so Var step (ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ) = ํ) = Var step (ํ | ํ)+Var step (ํ | ํ) = 2ํํ(ํ/(ํท/2))(1โํ/(ํท/2)). Substituting ํ = ํ(ํ,ํ+ํ) and averaging over realizations gives E[Var step (ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ))] = 2ํํ((2/ํท)ยทE[ํ(ํ,ํ+ํ)]โ(4/ ํท เฌถ )ยทE[ํ เฌถ (ํ,ํ+ํ)]). For the second term, use the conditional mean derived above, E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ)] = ฯ step ยทํ(ํ,ํ+ํ)+ํ: E[(E step [ํ(ํ,ํ+ํ+1) | ํ(ํ,ํ+ํ)]) เฌถ ] = E[(ฯ step ยทํ(ํ,ํ+ํ)+ํ) เฌถ ] = ฯ step เฌถ E[ํ เฌถ (ํ,ํ+ํ)]+2ฯ step ํยทE[ํ(ํ,ํ+ํ)]+ํ เฌถ . Adding the two terms yields the one-step recursion for E[ํ เฌถ (ํ,ํ+ํ+1)] in terms of E[ํ(ํ,ํ+ํ)] and E[ํ เฌถ (ํ,ํ+ํ)]. Iterating this recursion for ํ = 0,...,ํโํโ1 (starting from E[ํ(ํ,ํ)] = ํท/2 and E[ํ เฌถ (ํ,ํ)] = (ํท/2) เฌถ ) gives E[ํ เฌถ (ํ,ํ+(ํโํ))] = E[ํ เฌถ (ํ,ํ)], and then v th (ํ,ํ) follows from (3.8). Optional closed form for E[ํ เฌถ (ํ,ํ+ํ)]: Define ํด := ฯ step เฌถ โ(8ํํ)/ํท เฌถ and ํต := 2ฯ step ํ+(4ํํ)/ํท. Then the recursion above can be written as E[ํ เฌถ (ํ,ํ+ํ+1)] = ํดยทE[ํ เฌถ (ํ,ํ+ํ)]+ํตยทE[ํ(ํ,ํ+ํ)]+ํ เฌถ , with E[ํ(ํ,ํ+ํ)] = ํท/4+(ํท/ 4)ยทฯ step เฏ and E[ํ เฌถ (ํ,ํ)] = (ํท/2) เฌถ . The closed form is E[ํ เฌถ (ํ,ํ+ํ)] = ํด เฏ ยทE[ํ เฌถ (ํ,ํ)]+(ํตํท/4+ํ เฌถ )(ํด เฏ โ1)/(ํดโ1)+(ํตํท/4)ยท(ํด เฏ โฯ step เฏ )/(ํดโฯ step ), provided ํด โ 1 and ํด โ ฯ step ; otherwise use the corresponding limit (or iterate the one-step recursion, which is numerically stable for ํโํ โค ํ). 3.3 Finite-D Accuracy for Linear Similarity Family We use the evaluation protocol and error metrics of section 3.3. As above, assume ํ โค ํ and write ฮ = ํโํ. We derive bias th (ํ,ํ) and v th (ํ,ํ) for each linear derandomization variant, except for the deterministic equal-swap constructions Fixed-kpD Block-Swap and Float, for which ํ(ํ,ํ) = ํ lin (ํ,ํ) exactly. Therefore bias th (ํ,ํ) = 0 and v th (ํ,ํ) = 0, and hence BiasRMS th (ํ) = VarRMS th (ํ) = RMSE th (ํ) = 0. 3.3.1 Derandomization Variant Fixed-F (Linear) This derivation applies to the Fixed-F generators Fixed-F (Pool-Uniform) and Fixed-F (Perm- Scan). Let ํพ be the number of distinct components flipped between levels ํ and ํ; here ํพ = ฮยทํน exactly (for ฮ โค ํ). These components contribute 0 overlap because ํฅ เฏ (ํ) = 1โ 53 ํฅ เฏ (ํ). On the remaining ํทโํพ components, we have ํฅ เฏ (ํ) = ํฅ เฏ (ํ), so the overlap equals the count of ones in ํฅ เฏ over those indices. Although such components may have been flipped at earlier levels q < ํ, for each ํ the value ํฅ เฏ (ํ) equals either ํฅ เฌด (ํ) or 1โํฅ เฌด (ํ) depending on the flip parity up to level ํ; since ํฅ เฌด (ํ) are i.i.d. Bernoulli(1/2) and the update schedule is independent of ํฅ เฌด , it follows that ํฅ เฏ (ํ) are i.i.d. Bernoulli(1/2); in particular E[ํฅ เฏ (ํ)] = 1/2 for every ํ. Mean and bias: From E[ํฅ เฏ (ํ)] = 1/2 it follows that E[ํ(ํ,ํ)] = (ํทโํพ)/2 and hence ฮผ th (ํ,ํ) := E[ํ(ํ,ํ)] = 2ยทE[ํ(ํ,ํ)]/ํท = 1โํพ/ํท = 1โฮยทํน/ํท. With ํน = ํท/ํ, this equals 1โฮ/ํ, matching ํ lin (ฮ), so bias th (ํ,ํ) = 0. Finite-ํท variance: Restricting ํฅ เฏ (ํ) to the unchanged index set (of size ํทโํพ) preserves i.i.d. Bernoulli(1/2), hence ํ(ํ,ํ) is Binomial(ํทโํพ,1/2) and Var(ํ(ํ,ํ)) = (ํทโํพ)/4. Thus v th (ํ,ํ) := Var(ํ(ํ,ํ)) = 4ยทVar(ํ)/ํท เฌถ = (ํทโํพ)/ํท เฌถ = (1โฮยทํน/ํท)/ํท = (1โฮ/ ํ)/ํท. 3.3.2 Derandomization Variant Fixed-FpD (Linear) This derivation applies to the Fixed-FpD generators Fixed-FpD (Pool-Uniform) and Fixed- FpD (Perm-Scan). Mean and bias. The mean is identical to Fixed-F: ฮผ th (ํ,ํ) = 1โฮ/ํ, and so bias th (ํ,ํ) = 0. Finite-ํท variance. This differs from Fixed-F because |ํฅ เฌด | = ํท/2 induces dependence across coordinates. Let ํ เฏค denote the set of component indices flipped in the transition ํโํ+1 with |ํ เฏค | = ํน. Define the cumulative flipped set for any level ํ as ํต เฏค := โ เฏง = เฌด เฏคเฌฟเฌต ํ เฏง . Under the Linear no-reuse construction (disjoint per-level masks), ํต เฏ โ ํต เฏ and |ํต เฏค | = ํํน, so ํํน โค ํท. Define the following counts of initial ones: ํ เฏ := #ํ โ ํต เฏ : ํฅ เฌด (ํ) = 1 (number of ํฅ เฌด ones inside ํต เฏ ); ํ เฏ := #ํ โ ํต เฏ : ํฅ เฌด (ํ) = 1 (number of ํฅ เฌด ones inside ํต เฏ ). Partition components into three disjoint sets: (i) ํ โ ํต เฏ โํต เฏ : these components are flipped exactly once between levels ํ and ํ, hence ํฅ เฏ (ํ) = 1โํฅ เฏ (ํ). Therefore, they contribute 0 to overlap. (i) ํ โ ํต เฏ : these components were flipped before level ํ, hence ํฅ เฏ (ํ) = ํฅ เฏ (ํ) = 1โํฅ เฌด (ํ). They contribute the number of zeros of ํฅ เฌด inside ํต เฏ , which is |ํต เฏ |โํ เฏ . (i) ํ โ ํต เฏ : these components have not been flipped before level ํ, hence ํฅ เฏ (ํ) = ํฅ เฏ (ํ) = ํฅ เฌด (ํ). They contribute the number of ones of ํฅ เฌด outside ํต เฏ , which is ํท/2โํ เฏ . Summing the three contributions gives: ํ(ํ,ํ) = (ํท/2โํ เฏ )+(|ํต เฏ |โํ เฏ ) = ํท/2+ํํนโ (ํ เฏ +ํ เฏ ). Thus, Var(ํ(ํ,ํ)) = Var(ํ เฏ +ํ เฏ ) and v th (ํ,ํ) := Var(ํ(ํ,ํ)) = 4Var(ํ(ํ,ํ))/ํท เฌถ = 4Var(ํ เฏ +ํ เฏ )/ํท เฌถ (3.9) We now compute Var(ํ เฏ +ํ เฏ ). Using the law of total variance and conditioning on ํ เฏ gives Var(ํ เฏ +ํ เฏ ) = E[Var(ํ เฏ +ํ เฏ | ํ เฏ )]+Var(E[ํ เฏ +ํ เฏ | ํ เฏ ]). Because ํ เฏ is fixed under this conditioning, Var(ํ เฏ +ํ เฏ | ํ เฏ ) = Var(ํ เฏ | ํ เฏ ) and E[ํ เฏ +ํ เฏ | ํ เฏ ] = E[ํ เฏ | ํ เฏ ]+ํ เฏ . Therefore Var(ํ เฏ +ํ เฏ ) = E[Var(ํ เฏ | ํ เฏ )]+Var(E[ํ เฏ | ํ เฏ ]+ํ เฏ ). 54 Step ํ: ํ เฏ ~ Hypergeometric(ํท,ํท/2,ํํน), so Var(ํ เฏ ) = (ํํน/4)ยท(ํทโํํน)/(ํทโ1). Step 2: Conditional moments of ํ เฏ given ํ เฏ . The set ํต เฏ is the union of the first ํ masks and is a size-ํํน subset of ํต เฏ . Conditional on (ํต เฏ ,ํ เฏ ), the ํ เฏ ones are uniformly distributed over the ํํน positions of ํต เฏ . So ํ เฏ | (ํต เฏ ,ํ เฏ ) ~ Hypergeometric(|ํต เฏ | = ํํน,ํ เฏ ,|ํต เฏ | = ํํน). Hence E[ํ เฏ | (ํต เฏ ,ํ เฏ )] = ํํน (ํ เฏ /ํํน), Var(ํ เฏ | (ํต เฏ ,ํ เฏ )) = ํํน(ํ เฏ /ํํน)(1โํ เฏ /ํํน)(ํํนโํํน)/(ํํนโ1). These expressions depend only on ํ เฏ , ํํน, and ํํน (not on the particular indices in ํต เฏ ), therefore they also give E[ํ เฏ | ํ เฏ ] and Var(ํ เฏ | ํ เฏ ). Using ํ := ํํน (ํํนโํํน)/(ํํนโ1), we have Var(ํ เฏ | ํ เฏ ) = ํ (ํ เฏ /ํํน)(1โ ํ เฏ /ํํน). Since E[ํ เฏ ] = ํํน/2, we have E[(ํ เฏ /ํํน)(1โํ เฏ /ํํน)] = 1/4โVar(ํ เฏ )/(ํํน) เฌถ . Hence E[Var(ํ เฏ | ํ เฏ )] = ํ (1/4โVar(ํ เฏ )/(ํํน) เฌถ ). Also E[ํ เฏ | ํ เฏ ]+ํ เฏ = (ํํน/ํํน) ํ เฏ +ํ เฏ = (1+ํํน/ํํน)ํ เฏ , so Var(E[ํ เฏ | ํ เฏ ]+ํ เฏ ) = (1+ํํน/ํํน) เฌถ Var(ํ เฏ ). Therefore, Var(ํ เฏ +ํ เฏ ) = ํ (1/4โVar(ํ เฏ )/(ํํน) เฌถ )+(1+ํํน/ํํน) เฌถ Var(ํ เฏ ). Substituting ํ and Var(ํ เฏ ) into (3.9) gives v th (ํ,ํ)= ํท(3ํํน+ํํน)โ(ํํน+ํํน) เฌถ ํท เฌถ (ํทโ1) . 3.3.3 Derandomization Variant Fixed-pD (Linear) This derivation applies to the Fixed-pD generator Perm-Scan. The key difference from Fixed- F and Fixed-FpD is that the per-level requested flip count ํ เฏค is random rather than fixed, with E[ํ เฏค ] = ํท/ํ. Mean and bias: Let ํถ เฏค := ํ เฌด +...+ํ เฏคเฌฟเฌต . Under the Binomial proposed-count mechanism (Proposition 2), ํถ เฏค ~ Binomial(ํํท,1/ํ), and the cumulative number of distinct flipped components by level ํ is exactly |ํต เฏค | := min(ํท,ํถ เฏค ). Let ํพ be the number of newly flipped distinct components between levels ํ and ํ: ํพ := |ํต เฏ |โ|ํต เฏ |. Hence E[ํพ]= E[|ํต เฏ |]โE[|ํต เฏ |]. As in Fixed-F derivation, E[ํ(ํ,ํ) | ํพ] = 1โํพ/ํท. Therefore ฮผ th (ํ,ํ) = E[E[ํ(ํ,ํ)|ํพ]] = E[1โํพ/ํท] = 1โE[ํพ]/ํท and bias th (ํ,ํ) = ฮผ th (ํ,ํ)โ ํ lin (ฮ) = ฮ/ํโE[ํพ]/ํท. The required moments are evaluated exactly from ํถ เฏค ~ Binomial(ํํท,1/ํ) and |ํต เฏค | := min(ํท,ํถ เฏค ). In particular, E[|ํต เฏค | เฏก ] = ๏ฅ เฏ = เฌด เฎฝเฌฟเฌต ํ เฏก Pr(ํถ เฏค = j)+ํท เฏก Pr(ํถ เฏค โฅ D),ํ=1,2 and E[|ํต เฏ ||ํต เฏ |] = ํท เฌถ Pr(ํถ เฏ โฅ D)+๏ฅ เฏ = เฌด เฎฝเฌฟเฌต ํ Pr(ํถ เฏ = j)(ํ+ E[min(ํทโํ,๏ฅ เฏง = เฏ เฏเฌฟเฌต ํ เฏง ). Finite-D variance: Start from the law of total variance with respect to ํพ: Var(ํ(ํ,ํ)) = E[Var(ํ(ํ,ํ) | ํพ)]+Var(E[ํ(ํ,ํ) | ํพ]). For the first term, condition on |ํต เฏ | and |ํต เฏ |. Since ํต เฏ โ ํต เฏ and ํพ := |ํต เฏ |โ|ํต เฏ |, the Fixed-FpD calculation applies with ํํน and ํํน replaced by |ํต เฏ | and |ํต เฏ |, respectively: Var(ํ(ํ,ํ) | |ํต เฏ |,|ํต เฏ |)= ํท(3|ํต เฏ |+|ํต เฏ |)โ(|ํต เฏ |+|ํต เฏ |) เฌถ ํท เฌถ (ํทโ1) . 55 Because E[ํ(ํ,ํ) | |ํต เฏ |,|ํต เฏ |]=1โํพ/ํท depends on these two quantities only through ํพ, conditioning further on |ํต เฏ | and |ํต เฏ | introduces no additional conditional-mean variance. Hence, after averaging over ํพ, E[Var(ํ(ํ,ํ) | ํพ)]= ํท(3ํธ[|ํต เฏ |]+ํธ[|ํต เฏ |])โํธ[|ํต เฏ | เฌถ ]โ2E[|ํต เฏ ||ํต เฏ |]โE[|ํต เฏ | เฌถ ] ํท เฌถ (ํทโ1) . For the second term, since E[ํ(ํ,ํ) | ํพ] = 1โํพ/ํท, we have Var(E[ํ(ํ,ํ) | ํพ]) = Var(1โ ํพ/ํท) = Var(ํพ)/ํท เฌถ , where Var(ํพ)= E[|ํต เฏ | เฌถ ]+E[|ํต เฏ | เฌถ ]โ2 E[|ํต เฏ |โ|ํต เฏ |]โ(E[ํพ]) เฌถ ). Finally, v th (ํ,ํ) = E[Var(S(a,b) | K)]+Var(ํพ)/ํท เฌถ . 3.3.4 Derandomization Variant Baseline (Linear) Generators covered: Baseline (Perm-Scan). Mean and bias: As in the Fixed-pD derivation, bias th (ํ,ํ) = ฮ/ํโE[ํพ]/ํท, where the required expectation is evaluated exactly from the capped-binomial moments defined in the Fixed-pD section. Finite-D variance: Unlike Fixed-pD, the i.i.d. initialization of ํฑ เฌด in Baseline implies that, conditional on ํพ, the ํทโํพ unchanged components are independent Bernoulli(1/2); hence ํ(ํ,ํ) is Binomial(ํทโํพ,1/2). So E[ํ(ํ,ํ) | ํพ] = (ํทโํพ)/ํท and Var(ํ(ํ,ํ) | ํพ) = 4ยทVar(ํ(ํ,ํ)|ํพ)/ํท เฌถ = 4ยท(ํทโํพ)ยท(1/2) (1/2) / ํท เฌถ = (ํทโํพ)/ํท เฌถ . Apply the law of total variance over realizations of ํพ: Var(ํ(ํ,ํ)) = E[Var(ํ(ํ,ํ)|ํพ)]+Var(E[ํ(ํ,ํ)|ํพ]) = E[(ํทโํพ)/ํท เฌถ ]+Var(1โํพ/ํท) = (1โE[ํพ]/ํท)/ํท+Var(ํพ)/ํท เฌถ . Here E[ํพ] and Var(ํพ) are evaluated as in the Fixed-pD section. 56 4 Supplementary Note 4: Experiments 4.1 Supplementary Similarity Profiles This section complements section 7.1 with supplementary overlap- and Hamming-similarity profiles for the same generator families, using additional parameter settings and/or the same generators and seeds as in the main-text examples. 4.1.1 Exponential Similarity Family Figure S1 shows normalized Hamming similarity for the same exponential-family generators, seeds, anchors, and parameter settings as Figure 4 in section 7.1 (ํ = 0.01). Note that sim ham (ํ,ํ) = 1. We observe identical per-seed similarity curves for Baseline and Fixed-pD, and also for Fixed-F and Fixed-FpD. This per-seed equivalence occurs because these variant pairs use the same flip schedule between levels. Initialization constraints can change overlap similarity, because overlap depends on where the 1s are. However, for the same update-count schedule, they do not change the number of components that differ between two levels, so the Hamming similarity is unchanged. For Fixed-F and Fixed-FpD, deviations from the target law are visibly smaller, because the one-step Hamming distance is exactly ํน by construction; in Baseline and Fixed-pD the Bernoulli flip mask makes the per-step flip count random, which adds visible per-seed fluctuations around the target law. Fixed-kpD behaves most regularly, and coincides with the similarity curves for 2sim dot /ํท. Figures S2, S3 show the overlap- similarity and normalized Hamming-similarity profiles, respectively, at ํ = 0.1. 4.1.2 Linear Similarity Family Figure S4 shows normalized Hamming similarity for the same linear-family generators, seeds, anchors, and parameter settings as Figure 5 in the main text. Baseline and Fixed-pD share the same per-seed curves, while Fixed-F, Fixed-FpD, and Fixed-kpD share the exact linear curves. Fixed-F, Fixed-FpD, and Fixed-kpD give exact linear Hamming profiles because each transition flips exactly ํน previously unused components. 57 ํท = 200 ํท = 10000 (a) Hamming similarity, ํ = 0 . 01 (b) (c) (d) (e) Comparison level ํ Figure S1: Exponential-family similarity profiles (sim ham as a function of comparison level ํ) from 3 realizations (seeds), starting at anchors (0,33,67,100). Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000, ํ = 0.01. 58 ํท = 200 ํท = 10000 (a) Overlap similarity, ํ = 0 . 1 (b) (c) (d) (e) Comparison level ํ Figure S2: Exponential-family similarity profiles (2 sim dot /ํท as a function of comparison level ํ) from 3 realizations (seeds), starting at anchors (0,33,67,100). Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000, ํ = 0.1. 59 ํท = 200 ํท = 10000 (a) Hamming similarity, ํ = 0 . 1 (b) (c) (d) (e) Comparison level ํ Figure S3: Exponential-family similarity profiles (sim ham as a function of comparison level ํ) from 3 realizations (seeds), starting at anchors (0,33,67,100). Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000, ํ = 0.1. 60 ํท = 200 ํท = 10000 (a) Hamming similarity (b) (c) (d) (e) Comparison level ํ Figure S4: Linear-family similarity profiles (sim ham as a function of comparison level ํ) from 3 realizations (seeds), starting at anchors (0,33,67,100). Five generator constructions: Baseline (a), Fixed-pD (b), Fixed-F (c), Fixed-FpD (d), Fixed-kpD (e). ํ = 100, ํท โ 200,10000. 61 4.2 RMSE of Similarity: Experiments versus Theory This section reports additional RMSE tables corresponding to the experiments summarized in section 7.2, provides additional parameter settings and the interpretation of the trends. 4.2.1 Exponential Similarity Family Table S1: Exponential similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,33,67,100 and ํ โ 0.01,0.02,0.05,0.10,0.20. โMeanโ averages the anchor-wise RMSE values over the listed anchors. Parameters: ํท = 10000, ํ = 100, 10000 realizations. Theory rows are shown directly below the corresponding experimental rows. Variant Generator ํ ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline 0.01 0.009534 0.009757 0.009727 0.009519 0.009634 1 Baseline 0.02 0.009236 0.009438 0.009506 0.009132 0.009328 1 Baseline 0.05 0.008861 0.009081 0.009096 0.008866 0.008976 1 Baseline 0.10 0.008774 0.008838 0.008806 0.008760 0.008795 1 Baseline 0.20 0.008709 0.008727 0.008716 0.008675 0.008707 1 theory Baseline 0.01 0.009507 0.009748 0.009748 0.009507 0.009628 1 theory Baseline 0.02 0.009166 0.009463 0.009463 0.009166 0.009314 1 theory Baseline 0.05 0.008868 0.009050 0.009050 0.008868 0.008959 1 theory Baseline 0.10 0.008763 0.008850 0.008850 0.008763 0.008807 1 theory Baseline 0.20 0.008709 0.008744 0.008744 0.008709 0.008727 2 Fixed-pD 0.01 0.006169 0.008439 0.009085 0.009076 0.008192 2 Fixed-pD 0.02 0.006613 0.009058 0.009305 0.008985 0.008490 2 Fixed-pD 0.05 0.006897 0.008964 0.008992 0.008799 0.008413 2 Fixed-pD 0.10 0.006980 0.008779 0.008847 0.008734 0.008335 2 Fixed-pD 0.20 0.007017 0.008663 0.008693 0.008675 0.008262 2 theory Fixed-pD 0.01 0.006141 0.008440 0.009036 0.008997 0.008153 2 theory Fixed-pD 0.02 0.006610 0.009029 0.009246 0.008981 0.008466 2 theory Fixed-pD 0.05 0.006884 0.008968 0.008978 0.008795 0.008406 2 theory Fixed-pD 0.10 0.006973 0.008811 0.008811 0.008724 0.008330 2 theory Fixed-pD 0.20 0.007016 0.008722 0.008722 0.008687 0.008287 3 Fixed-F 0.01 0.009292 0.009429 0.009429 0.009288 0.009360 3 Fixed-F 0.02 0.009046 0.009245 0.009183 0.009034 0.009127 3 Fixed-F 0.05 0.008794 0.008939 0.008960 0.008834 0.008882 3 Fixed-F 0.10 0.008737 0.008739 0.008783 0.008734 0.008748 3 Fixed-F 0.20 0.008698 0.008698 0.008706 0.008693 0.008699 3 theory Fixed-F 0.01 0.009202 0.009372 0.009372 0.009202 0.009287 3 theory Fixed-F 0.02 0.008993 0.009169 0.009169 0.008993 0.009081 3 theory Fixed-F 0.05 0.008795 0.008906 0.008906 0.008795 0.008850 3 theory Fixed-F 0.10 0.008724 0.008772 0.008772 0.008724 0.008748 3 theory Fixed-F 0.20 0.008687 0.008699 0.008699 0.008687 0.008693 4 Fixed-FpD 0.01 0.005671 0.007896 0.008605 0.008640 0.007703 62 4 Fixed-FpD 0.02 0.006368 0.008629 0.008839 0.008782 0.008155 4 Fixed-FpD 0.05 0.006779 0.008770 0.008844 0.008677 0.008268 4 Fixed-FpD 0.10 0.006934 0.008749 0.008737 0.008658 0.008270 4 Fixed-FpD 0.20 0.006987 0.008707 0.008662 0.008649 0.008251 4 theory Fixed-FpD 0.01 0.005657 0.008003 0.008630 0.008674 0.007741 4 theory Fixed-FpD 0.02 0.006367 0.008721 0.008946 0.008804 0.008209 4 theory Fixed-FpD 0.05 0.006789 0.008822 0.008832 0.008720 0.008291 4 theory Fixed-FpD 0.10 0.006924 0.008733 0.008733 0.008684 0.008268 4 theory Fixed-FpD 0.20 0.006989 0.008677 0.008677 0.008665 0.008252 5 Fixed-kpD 0.01 0.003614 0.002724 0.002733 0.003597 0.003167 5 Fixed-kpD 0.02 0.004323 0.003675 0.003691 0.004299 0.003997 5 Fixed-kpD 0.05 0.004744 0.004490 0.004486 0.004734 0.004613 5 Fixed-kpD 0.10 0.004857 0.004740 0.004738 0.004860 0.004799 5 Fixed-kpD 0.20 0.004920 0.004865 0.004873 0.004923 0.004895 5 theory Fixed-kpD 0.01 0.003626 0.002748 0.002748 0.003626 0.003187 5 theory Fixed-kpD 0.02 0.004324 0.003698 0.003698 0.004324 0.004011 5 theory Fixed-kpD 0.05 0.004733 0.004478 0.004478 0.004733 0.004605 5 theory Fixed-kpD 0.10 0.004861 0.004743 0.004743 0.004861 0.004802 5 theory Fixed-kpD 0.20 0.004922 0.004869 0.004869 0.004922 0.004895 Table S2: Exponential similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,7,13,20 and ํ โ 0.01,0.02,0.05,0.10,0.20. โMeanโ averages RMSE over the anchors. Parameters: ํท = 200, ํ = 20, 10000 realizations. Theory rows are shown directly below the corresponding experimental rows. Variant Generator ํ ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline 0.01 0.069990 0.070443 0.070471 0.070029 0.070233 1 Baseline 0.02 0.069192 0.070471 0.070222 0.069411 0.069824 1 Baseline 0.05 0.067159 0.069265 0.068889 0.067177 0.068123 1 Baseline 0.10 0.064580 0.066283 0.066297 0.064391 0.065388 1 Baseline 0.20 0.062802 0.063900 0.063765 0.062674 0.063285 1 theory Baseline 0.01 0.070344 0.070574 0.070574 0.070344 0.070459 1 theory Baseline 0.02 0.069576 0.070243 0.070243 0.069576 0.069909 1 theory Baseline 0.05 0.067087 0.068808 0.068808 0.067087 0.067947 1 theory Baseline 0.10 0.064610 0.066552 0.066552 0.064610 0.065581 1 theory Baseline 0.20 0.062886 0.063988 0.063988 0.062886 0.063437 2 Fixed-pD 0.01 0.027994 0.037622 0.042760 0.046808 0.038796 2 Fixed-pD 0.02 0.035522 0.048167 0.053695 0.056630 0.048504 2 Fixed-pD 0.05 0.043497 0.060161 0.063309 0.062809 0.057444 2 Fixed-pD 0.10 0.046591 0.063618 0.064789 0.062933 0.059483 2 Fixed-pD 0.20 0.048205 0.063254 0.063188 0.062249 0.059224 2 theory Fixed-pD 0.01 0.027939 0.037313 0.042415 0.046449 0.038529 2 theory Fixed-pD 0.02 0.035425 0.048147 0.053584 0.056716 0.048468 63 2 theory Fixed-pD 0.05 0.043370 0.060265 0.063834 0.063591 0.057765 2 theory Fixed-pD 0.10 0.046576 0.063916 0.065021 0.063262 0.059694 2 theory Fixed-pD 0.20 0.048104 0.063184 0.063254 0.062142 0.059171 3 Fixed-F 0.01 0.067897 0.068502 0.068681 0.067513 0.068148 3 Fixed-F 0.02 0.066774 0.068452 0.068461 0.067436 0.067781 3 Fixed-F 0.05 0.064483 0.066176 0.066365 0.065058 0.065520 3 Fixed-F 0.10 0.063150 0.064193 0.064421 0.063198 0.063741 3 Fixed-F 0.20 0.062106 0.062484 0.062649 0.062134 0.062343 3 theory Fixed-F 0.01 0.068162 0.069050 0.069050 0.068162 0.068606 3 theory Fixed-F 0.02 0.066808 0.067900 0.067900 0.066808 0.067354 3 theory Fixed-F 0.05 0.064891 0.065926 0.065926 0.064891 0.065409 3 theory Fixed-F 0.10 0.063325 0.064251 0.064251 0.063325 0.063788 3 theory Fixed-F 0.20 0.062146 0.062528 0.062528 0.062146 0.062337 4 Fixed-FpD 0.01 0.021855 0.034246 0.039686 0.043175 0.034740 4 Fixed-FpD 0.02 0.029659 0.044771 0.050428 0.052926 0.044446 4 Fixed-FpD 0.05 0.039868 0.056955 0.060582 0.061224 0.054657 4 Fixed-FpD 0.10 0.044793 0.061338 0.062682 0.062097 0.057728 4 Fixed-FpD 0.20 0.047131 0.061349 0.061958 0.061586 0.058006 4 theory Fixed-FpD 0.01 0.021906 0.034416 0.039906 0.043148 0.034844 4 theory Fixed-FpD 0.02 0.029654 0.044737 0.050548 0.053348 0.044572 4 theory Fixed-FpD 0.05 0.039907 0.057010 0.060754 0.061293 0.054741 4 theory Fixed-FpD 0.10 0.044786 0.061540 0.062674 0.061957 0.057739 4 theory Fixed-FpD 0.20 0.047137 0.061710 0.061781 0.061396 0.058006 5 Fixed-kpD 0.01 0.009452 0.005695 0.005666 0.009426 0.007560 5 Fixed-kpD 0.02 0.015877 0.010271 0.010282 0.015737 0.013042 5 Fixed-kpD 0.05 0.025580 0.019329 0.019330 0.025739 0.022495 5 Fixed-kpD 0.10 0.030465 0.026075 0.026240 0.030640 0.028355 5 Fixed-kpD 0.20 0.032633 0.030875 0.030685 0.032577 0.031692 5 theory Fixed-kpD 0.01 0.009408 0.005695 0.005695 0.009408 0.007551 5 theory Fixed-kpD 0.02 0.015851 0.010254 0.010254 0.015851 0.013052 5 theory Fixed-kpD 0.05 0.025572 0.019262 0.019262 0.025572 0.022417 5 theory Fixed-kpD 0.10 0.030413 0.026196 0.026196 0.030413 0.028305 5 theory Fixed-kpD 0.20 0.032708 0.030718 0.030718 0.032708 0.031713 Table S3: Exponential similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,7,13,20 and ํ โ 0.01,0.02,0.05,0.10,0.20. โMeanโ averages RMSE over the anchors. Parameters: ํท = 10000, ํ = 20, 10000 realizations. Theory rows are shown directly below the corresponding experimental rows. Variant Generator ํ ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline 0.01 0.009998 0.010024 0.010011 0.009966 0.010000 1 Baseline 0.02 0.009877 0.009943 0.009906 0.009813 0.009885 64 1 Baseline 0.05 0.009497 0.009730 0.009750 0.009485 0.009616 1 Baseline 0.10 0.009148 0.009402 0.009400 0.009131 0.009270 1 Baseline 0.20 0.008907 0.009100 0.009054 0.008902 0.008991 1 theory Baseline 0.01 0.009948 0.009981 0.009981 0.009948 0.009964 1 theory Baseline 0.02 0.009840 0.009934 0.009934 0.009840 0.009887 1 theory Baseline 0.05 0.009488 0.009731 0.009731 0.009488 0.009609 1 theory Baseline 0.10 0.009137 0.009412 0.009412 0.009137 0.009275 1 theory Baseline 0.20 0.008893 0.009049 0.009049 0.008893 0.008971 2 Fixed-pD 0.01 0.003993 0.005334 0.006073 0.006626 0.005507 2 Fixed-pD 0.02 0.005027 0.006832 0.007622 0.008076 0.006889 2 Fixed-pD 0.05 0.006181 0.008545 0.009080 0.009006 0.008203 2 Fixed-pD 0.10 0.006575 0.009017 0.009182 0.008926 0.008425 2 Fixed-pD 0.20 0.006807 0.008980 0.008996 0.008817 0.008400 2 theory Fixed-pD 0.01 0.003951 0.005277 0.005998 0.006569 0.005449 2 theory Fixed-pD 0.02 0.005010 0.006809 0.007578 0.008021 0.006854 2 theory Fixed-pD 0.05 0.006133 0.008523 0.009027 0.008993 0.008169 2 theory Fixed-pD 0.10 0.006587 0.009039 0.009195 0.008947 0.008442 2 theory Fixed-pD 0.20 0.006803 0.008936 0.008946 0.008788 0.008368 3 Fixed-F 0.01 0.009719 0.009842 0.009872 0.009715 0.009787 3 Fixed-F 0.02 0.009505 0.009640 0.009605 0.009543 0.009573 3 Fixed-F 0.05 0.009136 0.009311 0.009283 0.009172 0.009226 3 Fixed-F 0.10 0.008943 0.009039 0.009107 0.008931 0.009005 3 Fixed-F 0.20 0.008788 0.008843 0.008885 0.008857 0.008843 3 theory Fixed-F 0.01 0.009639 0.009765 0.009765 0.009639 0.009702 3 theory Fixed-F 0.02 0.009447 0.009602 0.009602 0.009447 0.009525 3 theory Fixed-F 0.05 0.009176 0.009322 0.009322 0.009176 0.009249 3 theory Fixed-F 0.10 0.008955 0.009085 0.009085 0.008955 0.009020 3 theory Fixed-F 0.20 0.008788 0.008842 0.008842 0.008788 0.008815 4 Fixed-FpD 0.01 0.003085 0.004834 0.005607 0.006038 0.004891 4 Fixed-FpD 0.02 0.004179 0.006270 0.007050 0.007473 0.006243 4 Fixed-FpD 0.05 0.005630 0.008035 0.008585 0.008652 0.007726 4 Fixed-FpD 0.10 0.006341 0.008764 0.008834 0.008749 0.008172 4 Fixed-FpD 0.20 0.006648 0.008676 0.008741 0.008658 0.008181 4 theory Fixed-FpD 0.01 0.003092 0.004857 0.005633 0.006091 0.004918 4 theory Fixed-FpD 0.02 0.004187 0.006315 0.007138 0.007535 0.006294 4 theory Fixed-FpD 0.05 0.005639 0.008053 0.008585 0.008663 0.007735 4 theory Fixed-FpD 0.10 0.006331 0.008698 0.008861 0.008760 0.008163 4 theory Fixed-FpD 0.20 0.006665 0.008725 0.008736 0.008682 0.008202 5 Fixed-kpD 0.01 0.001325 0.000800 0.000800 0.001328 0.001063 5 Fixed-kpD 0.02 0.002228 0.001438 0.001449 0.002224 0.001835 5 Fixed-kpD 0.05 0.003614 0.002709 0.002697 0.003626 0.003162 5 Fixed-kpD 0.10 0.004265 0.003712 0.003688 0.004280 0.003986 65 5 Fixed-kpD 0.20 0.004625 0.004344 0.004348 0.004625 0.004486 5 theory Fixed-kpD 0.01 0.001325 0.000802 0.000802 0.001325 0.001063 5 theory Fixed-kpD 0.02 0.002232 0.001444 0.001444 0.002232 0.001838 5 theory Fixed-kpD 0.05 0.003604 0.002713 0.002713 0.003604 0.003159 5 theory Fixed-kpD 0.10 0.004289 0.003692 0.003692 0.004289 0.003990 5 theory Fixed-kpD 0.20 0.004613 0.004331 0.004331 0.004613 0.004472 4.2.2 Discussion Across all exponential derandomization variants and flip-rate settings ํ, the theoretical predictions closely track the experimental RMSE values in Table 3, both in overall magnitude and in the systematic anchor-to-anchor differences. RMSE decreases in the order Baseline โ Fixed-F > Fixed-pD > Fixed-FpD > Fixed-kpD. The main reason for the pattern Baseline โ Fixed-F > Fixed-pD is constant-weight initialization |ํฑ เฌด | = ํท/2 of Fixed-pD. In Baseline and Fixed-F, random initialization produces a realization-dependent offset in the similarity curve, which increases variance across realizations. This appears to be the dominant error contribution, keeping Fixed-F close to Baseline. Anchor-dependent variations arise because anchor-wise RMSE averages over comparison levels ํ, so different anchors produce different distributions of separations ฮ. Interior anchors contain a larger proportion of small-separation comparisons, whereas endpoint anchors contain a larger proportion of large-separation comparisons. Therefore, the direction and magnitude of the anchor effect depend on how each generatorโs per-separation squared- error contribution varies with ฮ. Baseline and Fixed-F use Bernoulli(1/2) initialization, so the separation dependence in the finite-D variance contains an explicit Bernoulli-start term Var(ํด เฏ +ํด เฏ ) = 2ํท+2ํทยทฯ step ฮ . This term is largest at ฮ = 0 and decays as ฮ increases, while the remaining contribution Var(ํถ ab ) approaches a nearly ฮ-independent long-separation regime. Consequently, over the relevant range of ฮ, the per-separation error contribution is slightly larger at small ฮ than at large ฮ, so interior anchors (which contain a larger proportion of small-ฮ comparisons) exhibit slightly larger anchor-wise RMSE emp (ํ) than endpoint anchors. Fixed-pD and Fixed-FpD use constant Hamming-weight initialization. Here the dominant anchor-to-anchor difference is driven by the special role of level 0. Var(ํด เฏ +ํด เฏ ) takes the form ํท(2โฮณ step เฏ โฮณ step เฏ +2ฯ step ฮ (1โฮณ step เฏญ )) with z = min(ํ,ํ). With ํ = 0, we have ํง = 0 for every ํ, so (1โฮณ step เฏญ ) = 0 and this distance-dependent contribution is suppressed uniformly across ํ, reducing overlap variability and lowering RMSE emp (0). For ํ > 0, this suppression does not apply in the same way, so the remaining anchors cluster at a higher, typical RMSE level; any additional effect of the separation distribution for endpoints versus interior anchors is secondary to this ํ = 0 effect. Fixed-kpD preserves constant |ํฑ เฏค | = ํท/2 for all levels ํ, so ํ(ํ,ํ) = 1 exactly and the ฮ = 0 error contribution is strongly suppressed. As ฮ increases, successive equal-swap 66 updates make the overlap increasingly variable and it approaches its long-separation regime, so the per-separation error contribution is larger at larger ฮ. Endpoint anchors (which contain a larger proportion of large-ฮ comparisons) therefore have larger anchor-wise RMSE emp (ํ) than interior anchors, opposite to Baseline and Fixed-F. Dependence on ํ. As ํ increases, ฯ step decreases in magnitude, so the mean/variance terms involving powers of ฯ step (and ฮณ step ) reach their long-separation regime at smaller ฮ. As a result, the pair-wise error depends less on separation ฮ over the evaluated range, and the differences in separation distributions of endpoint and interior anchors have less impact; the spread across endpoint and interior anchors narrows. 4.2.3 Linear Similarity Family Table S4: Linear similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,33,67,100. Parameters: ํท = 10000, ํ = 100, 10000 realizations. Bias is reported for Baseline and Fixed-ํํท. Theory rows are shown directly below the corresponding experimental rows for each generator. RMSE Variant Generator ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline (Pool-Bernoulli) 0.009980 0.009991 0.009964 0.009925 0.009965 1 Baseline (Perm-Scan) 0.009987 0.009980 0.009993 0.010007 0.009992 1 theory Baseline (Perm-Scan) 0.009937 0.009970 0.009993 0.009956 0.009964 2 Fixed-pD (Pool-Bernoulli) 0.008067 0.009322 0.009308 0.008035 0.008683 2 Fixed-pD (Perm-Scan) 0.008114 0.009450 0.009438 0.008157 0.008790 2 theory Fixed-pD (Perm-Scan) 0.008077 0.009381 0.009405 0.008125 0.008747 3 Fixed-F (Pool-Uniform) 0.007113 0.008513 0.008507 0.007107 0.007810 3 Fixed-F (Perm-Scan) 0.007025 0.008446 0.008523 0.007063 0.007764 3 theory Fixed-F (Perm-Scan) 0.007071 0.008479 0.008479 0.007071 0.007775 4 Fixed-FpD (Pool-Uniform) 0.004069 0.007824 0.007778 0.004069 0.005935 4 Fixed-FpD (Perm-Scan) 0.004074 0.007766 0.007817 0.004074 0.005933 4 theory Fixed-FpD (Perm-Scan) 0.004062 0.007779 0.007779 0.004062 0.005920 5 Fixed-kpD (Block-Swap) 0.000000 0.000000 0.000000 0.000000 0.000000 5 Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 5 theory Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 Bias Variant Generator ํ = 0 ํ = 33 ํ = 67 ํ = 100 Mean 1 Baseline (Pool-Bernoulli) 0.000396 0.000411 0.000410 0.003784 0.001250 1 Baseline (Perm-Scan) 0.000407 0.000412 0.000417 0.003994 0.001308 1 theory Baseline (Perm-Scan) 0.000403 0.000403 0.000403 0.003942 0.001288 67 2 Fixed-pD (Pool-Bernoulli) 0.000393 0.000400 0.000398 0.003880 0.001268 2 Fixed-pD (Perm-Scan) 0.000412 0.000419 0.000416 0.003952 0.001300 2 theory Fixed-pD (Perm-Scan) 0.000403 0.000403 0.000403 0.003942 0.001288 Table S5: Linear similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,7,13,20. Parameters: ํท = 200, ํ = 20, 10000 realizations. Bias is reported for Baseline and Fixed-ํํท. Theory rows are shown directly below the corresponding experimental rows for each generator. RMSE Variant Generator ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline (Pool-Bernoulli) 0.068257 0.069488 0.070334 0.068268 0.069087 1 Baseline (Perm-Scan) 0.068546 0.069521 0.070535 0.069300 0.069476 1 theory Baseline (Perm-Scan) 0.068332 0.069673 0.070474 0.069197 0.069419 2 Fixed-pD (Pool-Bernoulli) 0.053810 0.064403 0.065629 0.054900 0.059686 2 Fixed-pD (Perm-Scan) 0.054832 0.065661 0.066467 0.057382 0.061086 2 theory Fixed-pD (Perm-Scan) 0.054348 0.065366 0.066158 0.056626 0.060625 3 Fixed-F (Pool-Uniform) 0.049897 0.059967 0.059958 0.049912 0.054934 3 Fixed-F (Perm-Scan) 0.050201 0.060263 0.059898 0.049782 0.055036 3 theory Fixed-F (Perm-Scan) 0.050000 0.059861 0.059861 0.050000 0.054930 4 Fixed-FpD (Pool-Uniform) 0.028381 0.055694 0.055334 0.028381 0.041947 4 Fixed-FpD (Perm-Scan) 0.028074 0.054487 0.054903 0.028074 0.041384 4 theory Fixed-FpD (Perm-Scan) 0.028207 0.055024 0.055024 0.028207 0.041616 5 Fixed-kpD (Block-Swap) 0.000000 0.000000 0.000000 0.000000 0.000000 5 Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 5 theory Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 Bias Variant Generator ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline (Pool-Bernoulli) 0.005961 0.006220 0.006282 0.025398 0.010965 1 Baseline (Perm-Scan) 0.006569 0.006411 0.006444 0.026695 0.011530 1 theory Baseline (Perm-Scan) 0.006329 0.006329 0.006329 0.026345 0.011333 2 Fixed-pD (Pool-Bernoulli) 0.005841 0.005883 0.005665 0.024420 0.010452 2 Fixed-pD (Perm-Scan) 0.006588 0.006495 0.006460 0.026964 0.011627 2 theory Fixed-pD (Perm-Scan) 0.006329 0.006329 0.006329 0.026345 0.011333 Table S6: Linear similarity family. RMSE emp (ํ) and RMSE th (ํ) for anchors ํ โ 0,7,13,20. Parameters: ํท = 10000, ํ = 20, 10000 realizations. Bias is reported for Baseline and Fixed- 68 ํํท. Theory rows are shown directly below the corresponding experimental rows for each generator. RMSE Variant Generator ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline (Pool-Bernoulli) 0.009668 0.009825 0.009844 0.009526 0.009716 1 Baseline (Perm-Scan) 0.009788 0.009894 0.009972 0.009883 0.009884 1 theory Baseline (Perm-Scan) 0.009760 0.009896 0.009964 0.009778 0.009849 2 Fixed-pD (Pool-Bernoulli) 0.007701 0.009185 0.009283 0.007492 0.008415 2 Fixed-pD (Perm-Scan) 0.007789 0.009342 0.009403 0.007885 0.008605 2 theory Fixed-pD (Perm-Scan) 0.007815 0.009301 0.009374 0.007864 0.008589 3 Fixed-F (Pool-Uniform) 0.007042 0.008374 0.008420 0.007118 0.007739 3 Fixed-F (Perm-Scan) 0.007025 0.008436 0.008493 0.007063 0.007754 3 theory Fixed-F (Perm-Scan) 0.007071 0.008466 0.008466 0.007071 0.007768 4 Fixed-FpD (Pool-Uniform) 0.003960 0.007685 0.007728 0.003960 0.005834 4 Fixed-FpD (Perm-Scan) 0.003991 0.007772 0.007799 0.003991 0.005888 4 theory Fixed-FpD (Perm-Scan) 0.003979 0.007762 0.007762 0.003979 0.005871 5 Fixed-kpD (Block-Swap) 0.000000 0.000000 0.000000 0.000000 0.000000 5 Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 5 theory Fixed-kpD (Float) 0.000000 0.000000 0.000000 0.000000 0.000000 Bias Variant Generator ํ = 0 ํ = 7 ํ = 13 ํ = 20 Mean 1 Baseline (Pool-Bernoulli) 0.000795 0.000803 0.000796 0.003547 0.001485 1 Baseline (Perm-Scan) 0.000842 0.000868 0.000877 0.003826 0.001603 1 theory Baseline (Perm-Scan) 0.000849 0.000849 0.000849 0.003795 0.001585 2 Fixed-pD (Pool-Bernoulli) 0.000796 0.000814 0.000805 0.003597 0.001503 2 Fixed-pD (Perm-Scan) 0.000848 0.000857 0.000862 0.003791 0.001589 2 theory Fixed-pD (Perm-Scan) 0.000849 0.000849 0.000849 0.003795 0.001585 4.2.4 Discussion Across the generators listed for each derandomization variant in Table 4, the theoretical predictions match the experiments well in both overall RMSE and anchor-dependent trends. RMSE decreases in the order Baseline > Fixed-pD > Fixed-F > Fixed-FpD > Fixed-kpD. The fixed-count variants (Fixed-F, Fixed-FpD, Fixed-kpD) are essentially unbiased, whereas the random-count variants (Baseline, Fixed-pD) exhibit nonzero bias due to finite-capacity effects near level ํ. Fixed-kpD (Block-Swap / Float) is deterministic by construction and matches the linear target exactly, so both bias and variance vanish (RMSE is zero up to numerical precision). 69 To understand Fixed-pD > Fixed-F, note that the key difference is whether the number ํพ of newly flipped components between levels is deterministic. Fixed-F has ํพ = ฮF, removing the additional Var(ํพ)/ํท เฌถ contribution present when ํพ is random, so bias is near zero and variance is smaller. Fixed-pD retains random per-level proposed count together with the โcannot exceed ํทโ constraint near level ํ, which induces extra bias near the end of the axis and extra variance through randomness in ํพ. Concerning anchor dependence, for Fixed-F and Fixed-FpD, the finite-D variance decreases linearly with separation ฮ through the factor ํทโฮF: as ฮ grows, fewer components remain unchanged and able to contribute overlap, so Var(ํ(ํ,ํ)) drops accordingly. In Fixed- F, since interior anchors contain a larger proportion of small-separation comparisons under the ํ-averaging protocol, their anchor-wise average therefore contains a larger proportion of the higher-variance small-ฮ regime and therefore exhibits larger RMSE emp (ํ) than endpoint anchors. In Fixed-FpD, constant Hamming-weight initialization further suppresses overlap variability when one of the two levels is an endpoint ํ = 0 or ํ = ํ (both have ํท/2 ones by construction). Consequently RMSE emp (ํ) is noticeably smaller at endpoint anchors, and the endpoint/interior contrast is stronger than in Fixed-F. In Baseline and Fixed-pD variants, the per-level flip count is random and constrained by the remaining pool of not-yet-flipped components. This induces bias when one of the levels is close to ํ: the expected number of new distinct flips between two nearby levels falls below the ideal linear count ฮยท(ํท/ํ), so the mean similarity deviates from ํ lin . This effect is most visible for anchors near ํ, where many (ํ,ํ) pairs involve an โalmost fully flippedโ level. At the same time, the remaining-pool constraint reduces run-to-run randomness near pool exhaustion because fewer admissible choices remain, so the variance contribution decreases near ํ even while bias increases. Relative to Baseline, the constant Hamming-weight initialization of Fixed-pD reduces the overall variance while leaving the qualitative terminal- bias pattern unchanged. Across dimensionality ํท, RMSE follows the expected 1/โD scaling.