Neural-state segmentation stops rebuilding templates per candidate: reused interval statistics cut the same fit by up to 1,730 times
Synopsis
Greedy State Boundary Search (GSBS) finds transitions between stable neural activity patterns, but it rebuilt state templates and recomputed correlations for every candidate boundary, making analyses across recordings and settings expensive. HP-GSBS rewrites the matching objective as additive interval contributions and computes t-distance from reusable correlation statistics, adding streaming candidate reduction, sequential local refinement and active-block reuse across CPU, PyTorch CUDA and Triton paths. Across seven controlled workloads with two input realizations each, median same-input speedups range from 154 to 1,730, and all 168 optimized executions reproduce complete reference boundary histories and selected state counts, with a maximum absolute t-distance difference of 1.88×10⁻¹¹.
Interpretation
Neural-state segmentation can now reuse interval statistics already computed instead of rebuilding state templates and correlations for every candidate boundary. The original implementation reconstructed templates and recalculated correlations at each proposal, even though one insertion changes only a small part of the partition while other intervals keep their observations and state means. Across seven controlled workloads with two input realizations each, median same-input speedups range from 154 to 1,730; at the central configuration official GSBS takes 64.7 s, against 0.142 s for CPU, 0.081 s for PyTorch CUDA and 0.099 s for Triton.
The matching objective becomes a sum of temporal interval contributions, so each insertion replaces its parent interval's contribution with those of its children. Temporal prefixes supply these contributions, and the Full-Q route stores every valid interval score in a table, turning candidate scoring into a fixed number of lookups and scalar operations. All 168 optimized executions reproduce complete reference boundary histories and selected state counts, with identical state patterns and boundary strengths and a maximum absolute t-distance difference of 1.88×10⁻¹¹.
The t-distance used to compare partitions is aggregated from correlation statistics rather than rescanning the same time-pair correlations. T-distance depends only on counts, sums and squared sums of eligible correlations, and two-dimensional prefix tables return all six quantities for within-state and adjacent-state rectangles through four-corner queries. On four BBBD EEG matrices, CPU, PyTorch CUDA and Triton outputs match their respective reference records in complete boundary histories, with selected state counts of 120 to 173 and maximum absolute t-distance differences between 1.85×10⁻¹³ and 3.13×10⁻¹³.
Perspective
The demonstrated scope is seven controlled synthetic workloads, four BBBD EEG analysis matrices, and one 23.65-minute Sherlock fMRI dataset with 16 participants and 4,230 angular-gyrus voxels; the fMRI part uses one region of interest and a matching tolerance of ±3 TR (±4.5 s), with a null that preserves each participant's boundary count and circular spacing.
Several participants select 60 or 61 states, at the upper end of the evaluated search range, which the authors cite as motivation for wider Kmax sensitivity analyses; the low-memory route's measurements use single-boundary search, disabled refinement, block size zero and Kmax of 16, so its efficiency should be read against that workload definition.