Haplotype phasing means working out which variant letters sit together on the same physical copy of a chromosome. Sequencing machines report that a person carries both A and G at one position and both C and T at another, but not whether A travels with C or with T. Recent neural phasers solve this by grouping sequencing reads into $k$ clusters, one per chromosome copy. They spend the same computation on every stretch of the genome, whether that stretch is easy or hard. In a deep, variant-rich region almost any method gets the answer right. In a thin-coverage or repetitive region even the best method struggles and could use more search. This proposal treats phasing as a compute-allocation problem. A cheap phaser runs everywhere. A small, calibrated predictor then estimates, window by window, whether the expensive neural pipeline would change the cheap answer. Expensive compute goes only to those windows, and the compute saved is reinvested in the hardest ones.
Phasing has a property that most reasoning tasks used in adaptive-compute research lack. The supervision signal for "would more compute change the answer?" can be produced on unlabeled real data, by running the expensive pipeline offline and comparing. No ground-truth haplotypes are needed. That removes the main weakness of learned allocators, which depend on correctness verifiers during training. It also makes phasing a clean test of whether the gains reported for language-model test-time scaling carry over to a structured combinatorial problem where errors propagate along the chromosome.
Core Claim
On standard phasing benchmarks, most genomic windows get the same read partition from a cheap combinatorial phaser as from a full neural pipeline with restarts. We claim that a predictor trained on a self-supervised agreement label, with its routing threshold set by distribution-free calibration, can do two things. First, at a fraction of the compute, it can match the uniform pipeline on accuracy measured by Minimum Error Correction (MEC), the number of base edits needed to make every read agree with its assigned haplotype, and by Correct Phasing Rate (CPR). Second, at equal total compute, moving the saved budget into extra message-passing depth and restarts on the flagged windows should improve CPR and switch-error rate over uniform allocation. The second claim is the scientifically interesting one. The first is mostly an engineering win. If only the first holds, the paper is a speed paper, and we will say so.
Research Program
The work starts from the uniform neural phasers in the file. NeurHap (Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction) colors a read-overlap graph with a graph neural network (GNN). A GNN is a model that updates each node by passing messages from its neighbors. NeurHap then applies a local combinatorial refinement. XHap (XHap: haplotype assembly using long-distance read correlations learned by transformers) computes all-pairs read correlations with self-attention and clusters them with kernel $k$-means. CAECseq (A Convolutional Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction) and GAEseq (A Graph Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction) learn read clusters with auto-encoders. All four run a fixed amount of computation per read set. NeurHap explicitly concedes that massive long-read graphs strain its search. These papers motivate the gap and supply the expensive tier; we do not modify their models.
We build a three-tier ladder within one method family, NeurHap, and replicate it with CAECseq. The cheap tier is greedy read partitioning followed by NeurHap-refine local search, with no GNN. The middle tier is NeurHap-search at its default depth with a single run. The top tier uses deeper message passing and several random restarts, with the best MEC kept.
The genome is cut into windows at points of weak read linkage. Adjacent windows overlap by a few variant sites so that their phases can be stitched by majority agreement in the overlap. Switch errors introduced at window seams are measured separately, because a reviewer will rightly worry that windowing itself causes them. Windows are independent, so they batch cleanly on a GPU. This sidesteps the batching problems that per-token early exit causes in language models.
The allocation predictor borrows its target from Thought Calibration (Thought calibration: Efficient and confident test-time scaling). That paper found that a self-supervised "consistent with the maximum-budget answer" probe generalized across domains better than a correctness probe. For each training window we run all tiers. The label is whether the cheap partition agrees with the top-tier partition. Agreement is measured as the fraction of reads assigned identically after the best matching of haplotype labels, thresholded to "switch-free." Following Learning How Hard to Think: Input-Adaptive Allocation of LM Computation, which predicts the marginal gain of extra samples, we also regress the MEC reduction gained by escalating.
The predictor is a small multilayer perceptron. Its inputs deliberately include the obvious surface signals: coverage, heterozygous-site density, and the cheap tier's own per-read MEC residual and assignment margins. They also include the count of conflict edges left unresolved in the read graph and, optionally, NeurHap's embeddings after one message-passing round. We include the cheap solver's own residuals from the start because a residual-thresholding cascade is the strongest simple alternative. Building on it is more honest than arguing against it.
The routing threshold is set with Learn-then-Test calibration, as in Thought Calibration. The probability that a window routed to the cheap tier disagrees with the top tier is held below a user-chosen $\alpha$. This guarantee is relative to the expensive pipeline, not to biological truth. It holds only when calibration and deployment windows are exchangeable, and we test that assumption directly under shift.
For the fixed-budget regime, compute saved on easy windows is spent on flagged windows in order of predicted marginal MEC gain. Restarts are added in doubling rounds, borrowing the shell-doubling idea of ADAP (Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification). Restarts stop when partitions within a round agree, an Early-Stopping Self-Consistency-style rule (Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning).
Baselines
The do-nothing reference is the cheap tier run on every window. It sets the accuracy floor and the compute floor. If the learned allocator cannot clearly beat it on CPR in low-coverage settings, the expensive tiers are not earning their cost.
The strongest existing method is uniform NeurHap at default settings on the full read set. On the Sim-Potato tetraploid benchmark at 5x coverage, NeurHap reports an MEC of 29.9, against 96.2 for the next-best method, with a runtime of 258 seconds on the potato data versus 341 for CAECseq and 492 for GAEseq (Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction). We rerun it ourselves on the same windows, hardware and seeds, and compare against our reproduction rather than the reported figure. Uniform NeurHap with the top-tier depth and restarts everywhere serves as the accuracy ceiling at maximum compute.
On HIV-1 5-virus-mix, the strongest reported figure is CAECseq's perfect reconstruction of all strains in 9 of 13 genes (A Convolutional Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction). NeurHap reports an MEC about 160 points below its closest competitor there. For XHap on NA12878 and potato chromosome 5, no reported result was found on Lacuna, so we run it ourselves.
Beating uniform NeurHap means one of two outcomes. Either we match its MEC and CPR within run-to-run noise at no more than half its GPU-seconds. Or, at equal GPU-seconds, we exceed its CPR, with improvements concentrated on the 5x Sim-Potato setting and the HIV genes it fails.
The decisive ablations target the predictor. The first is a hand-set cascade that escalates any window whose cheap-tier per-read MEC residual exceeds a threshold tuned on the same calibration data. The second is a router using only coverage and site density. The third is our predictor without GNN embeddings. The fourth is an oracle router that knows the agreement label, which gives the ceiling on allocation gains. All routers get the same calibration windows, the same $\alpha$ and the same compute accounting. A second ablation swaps the agreement target for an MEC-gain target, to see whether the self-supervised label matters.
Why not just…?
Why not just threshold on coverage and variant density? These features are free. The PECAT results (De novo diploid genome assembly using long noisy reads) show that low divergence causes collapse, so density clearly carries signal. But noisy long reads blur true variants with sequencing errors, which is why PECAT needed a second assembly round to bring inconsistent overlaps from about 37% to about 1%. Raw density therefore likely misclassifies noisy windows. The coverage-and-density router is an explicit ablation. If it matches the learned router, we report that the cheap rule suffices.
Why not just escalate when the cheap solver's own MEC is high? This is the real threat. MEC is a free, local, built-in verifier. We therefore feed the residual into the predictor rather than competing against it. The open question is whether MEC alone suffices. At low coverage a partition can have low MEC and still be wrong, because few reads constrain it. That is exactly the regime where agreement with a deeper search should be more informative. If the hand-tuned residual cascade reaches the learned router's accuracy-compute curve, the contribution narrows to calibration and fixed-budget reallocation, and we will state that.
Why not just use fewer layers or fewer restarts everywhere? Uniform shrinking is the obvious way to buy speed. We run uniform budgets at matched average compute. Damani et al. found that adaptive allocation at a fixed budget improved success by up to 10% over uniform best-of-$k$. ADAP found that the best fixed-budget policy failed on 12–16% of problems at the cost where adaptive search reached full success. These results come from reasoning tasks. Whether phasing difficulty is heavy-tailed enough for the same effect to appear is precisely what the fixed-budget experiment measures.
Proposed Experiments
The first experiment establishes how much headroom exists. On Sim-Potato at 5x, 15x, 25x and 35x, and on HIV-1 5-virus-mix, we measure the fraction of windows where the cheap and top tiers agree, and the oracle router's accuracy-compute curve. If agreement is near 100% at high coverage and the oracle cannot beat uniform NeurHap at equal compute anywhere, the reallocation claim is dead, and only the speed claim is tested.
The second experiment compares accuracy-versus-GPU-seconds curves for every router in the Baselines section. Metrics are MEC, CPR, switch-error rate (including seam-attributed switches), perfect-gene count on HIV, and fraction of windows escalated.
The third experiment tests calibration under shift. We calibrate on Sim-Potato and deploy on real HIV-1, HCV and ZIKV mixtures, and report the realized disagreement rate against the target $\alpha$. Thought Calibration's out-of-distribution savings dropped from up to 60% to about 20%, and we expect a similar loss of coverage. Recalibration on unlabeled target windows is possible because the label needs no ground truth, and we test whether that recovers it.
The fourth experiment transfers the trained router, unchanged, to CAECseq and to XHap on NA12878. This shows whether the predictor learned a property of the windows or a quirk of NeurHap.
The project succeeds if, at equal compute, adaptive allocation beats uniform NeurHap on CPR in the low-coverage regime, with the realized disagreement rate within $\alpha$ in distribution.
References
- Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction
- XHap: haplotype assembly using long-distance read correlations learned by transformers
- A Convolutional Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction
- A Graph Auto-Encoder for Haplotype Assembly and Viral Quasispecies Reconstruction
- Thought calibration: Efficient and confident test-time scaling
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
- De novo diploid genome assembly using long noisy reads