Prospective Completion Prediction for Independent-Trial Cluster Search with Compositional State: Measurement Burden, a Pre-Outcome Separation Gate, and Structural Limits

Technical Summary: Prospective Completion Prediction for Independent-Trial Cluster Search

Problem Formulation
The paper addresses the challenge of predicting the completion time for independent-trial distributed search jobs (specifically SHA-256 hash searches) where a job concludes upon accumulating a $k$-th success. Unlike deterministic speedup models, this process is stochastic, governed by a known per-trial success probability ($p = 2^{-24}$ under an ideal-hash assumption) and variable worker performance.

The core systems problem is an information-selection trade-off: To predict completion accurately, a system needs to characterize the cluster's "productive capacity" (attempt rates) and "operational activation" (when workers become steady). However, acquiring highly specific state for every candidate placement incurs a high "measurement burden," potentially eroding the operational value of the prediction. The research asks: Which independently characterized state supports accurate prospective prediction? When does occupancy-aware rate redistribution offer design-relevant discrimination over equal aggregate capacity? And what structural conditions limit that discrimination?

Methodology
The authors propose a zero-fit analytic predictor. "Zero-fit" signifies that the predictor does not use target completion outcomes to calibrate or fit the model; it relies solely on independently characterized state (capacity and activation) and the known success probability $p$.

• State Representations:
  • M1: Coarse, pooled state using nominal size and pooled activation.
  • M2a: Uses target-placement aggregate capacity and target-specific activation.
  • M2b: Composes node-local capacities (measured at specific local occupancies) and assigns equal-share rates ($C(node, n)/n$) to workers, combined with target-specific activation.
  • U-EQ: An equalized capacity comparator for the unseen family.
• Experimental Phases:
  • P3 & P4-A: Prospective evaluations on measured configuration regimes (e.g., $N=6$ workers on 3 nodes).
  • UCV: A "structurally unseen" evaluation using a cyclic $\{3, 2, 1\}$ occupancy family. Predictions were frozen before outcomes were observed.
  • X411: A prospective "pre-outcome separation gate" using a fresh $\{4, 1, 1\}$ family. This phase was designed to stop before collecting target outcomes if the predicted difference between representations was insufficient.
• Metrics: Primary accuracy is measured by cell-mean Mean Absolute Percentage Error (MAPE) of total completion time. Burden is quantified in worker-hours required for characterization.

Key Results

1. Prediction Accuracy in Measured Regimes:

   • In the measured regimes (P3 and P4-A), the zero-fit predictor achieved low error rates. For P3, M2b achieved a MAPE of 1.56%. For P4-A, M2a and M2b achieved 2.54% and 2.67%, respectively.
   • Statistical testing (Holm-adjusted) showed no significant ordering between M2a and M2b in P4-A ($p = 0.1327$).

2. Characterization Burden and Reuse:

   • The M2b approach (node-local composition) reduced the total characterization burden by 35.52% compared to M2a/M1 in the P4 geometry.
   • Node-local capacity measurements were stable across homogeneous nodes for occupancies 1–3 but dropped significantly (to ~85% of the rate) at occupancy 4.
   • Composed node-local totals closely matched independently measured placement totals (max discrepancy 0.45%), validating the composition rule within the measured homogeneous pool.

3. Structural Limits and the "Unseen" Family (UCV):

   • On the structurally unseen $\{3, 2, 1\}$ family, M2b achieved a MAPE of 7.42%.
   • Crucially, the difference between the occupancy-aware M2b and the equalized EQ representation was negligible (mean absolute difference ~0.000246s). This was because the $\{3, 2, 1\}$ family only utilized occupancies 1–3, where capacity curves were nearly flat, offering little "leverage" to distinguish the representations.

4. The Pre-Outcome Gate (X411):

   • In the X411 campaign, the system characterized a fresh $\{4, 1, 1\}$ family (involving occupancy 4, where capacity drops).
   • The predicted separation between M2b and EQ passed the characterization-uncertainty relative-precision heuristic (resolvability ratio 2.45) but failed the prespecified experimental-design continuation threshold (0.164% separation vs. required 5%).
   • Consequently, the protocol authorized zero target completion runs. The campaign stopped before collecting any outcome data, demonstrating a "negative" design decision based purely on prospective state.

5. Structural Analysis:

   • Mathematical analysis revealed that discrimination between representations depends on the rate–activation interaction ($\text{Cov}(r, a)$).
   • Complete-path invariance (where different rate distributions yield identical completion times) requires a specific balance condition across activation groups, not just zero covariance.
   • Post-hoc diagnostics revealed substantial within-node worker-rate heterogeneity at occupancy 4, limiting the physical interpretation of the "equal-share" assumption used in M2b.

Claims and Significance
The paper makes modest, strictly bounded claims:

• Prospective Validity: Independently characterized state can support low-error prospective prediction for independent-trial workloads without fitting to target outcomes.
• Cost-Benefit of State: Finer state (node-local composition) is valuable not necessarily for superior accuracy (which was not statistically established over aggregate state in this regime) but for reducing measurement burden (35.52% reduction).
• Limits of Discriminability: The paper demonstrates that "finer" state is not automatically valuable. If the structural conditions (rate–activation interaction) do not create a design-relevant separation, acquiring that state is futile. The X411 gate successfully prevented a wasteful campaign by detecting this lack of separation prospectively.
• No Universal Generalization: The authors explicitly state that no results establish universal superiority, causal activation mechanisms, or generalization to arbitrary workloads or heterogeneous clusters. The UCV results are descriptive historical evidence, not prospective proof of generalization.
• Methodological Contribution: The study introduces a framework for separating "measurement burden" from "prediction accuracy" and establishes a "pre-outcome separation gate" to terminate campaigns where state representations are indistinguishable before incurring the cost of target execution.

In summary, the work argues that for independent-trial searches, the value of a predictive state representation is a function of its acquisition cost, its reusability, and its structural ability to interact with activation timing to produce a meaningful prediction shift—not merely its granularity.