Skip to content

Guard inverse-CDF resampling endpoints and conditional references - #202

Open
THargreaves wants to merge 1 commit into
mainfrom
th/systematic-endpoint
Open

THargreaves wants to merge 1 commit into
mainfrom
th/systematic-endpoint

Conversation

@THargreaves

Copy link
Copy Markdown
Collaborator

Systematic and stratified resampling scan the scaled cumulative weights vs = n * cumsum(w) with while vs[idx] <= u and no upper bound, inside @inbounds. When rounding puts a threshold at or beyond vs[end], the loop reads past the array. With 4096 exactly uniform Float32 weights and Xoshiro(3459), --check-bounds=yes throws a BoundsError at index 4097; without bounds checking the returned maximum ancestor was 4117.

Probing the conditional variants found a related defect. They could return idxs[1] != ref_idx, breaking the contract that conditional SMC relies on. With 64 particles and skewed weights (rand^4, normalised), the reference was lost in:

Float32 Float64
CPU systematic / stratified ~2.7% of draws ~0.02% of draws
GPU systematic / stratified ~2.7% of draws ~0.02% of draws

Most losses are references whose weight is below the resolution of the cumulative weights, so their interval has zero width. The rest come from rounding in the reference offset, which can step past a narrow interval.

Changes:

  • Endpoint guard: the four CPU scans stop at the last particle with positive weight. This also keeps trailing zero-weight particles from being selected.
  • Reference slot: CPU and GPU conditional systematic/stratified resampling assign the reference slot directly, as the GPU multinomial method already did. This corrects rounding only; the law of the other slots is unchanged.
  • Scaling: the cumulative weights are scaled in place (vs .*= n).

Tests added, independent of RNG stream:

  • weights summing to 0.6 with trailing zeros, so thresholds lie past the CDF;
  • a reference with weight 1f-10 between two halves, on CPU and GPU.

All fail before the fix and pass after it. The full CPU suite passes locally (3351 tests), as does test/components/resamplers.jl including GPU items on an RTX 4090.

Systematic and stratified resampling scanned the scaled cumulative weights
without an upper bound. When rounding put a threshold at or beyond the final
cumulative weight, as with 4096 uniform Float32 weights, the @inbounds loop
read past the array. Scans now stop at the last particle with positive weight,
which also keeps trailing zero-weight particles from being selected.

Conditional systematic and stratified resampling could lose the reference: a
reference whose weight is below the resolution of the cumulative weights has a
zero-width interval, and rounding in the reference offset can step past a
narrow one. The reference slot is now assigned directly on CPU and GPU. This
corrects rounding only; the law of the remaining slots is unchanged.
@codecov

codecov Bot commented Nov 9, 2026

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 81.81818% with 6 lines in your changes missing coverage. Please review.
✅ Project coverage is 71.97%. Comparing base (c4194c8) to head (c97513c).

Files with missing lines Patch % Lines
GeneralisedFilters/ext/CUDAExt.jl 0.00% 6 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main     #202      +/-   ##
==========================================
+ Coverage   71.95%   71.97%   +0.02%     
==========================================
  Files         104      104              
  Lines        4136     4157      +21     
==========================================
+ Hits         2976     2992      +16     
- Misses       1160     1165       +5     
Flag Coverage Δ
GeneralisedFilters 72.40% <81.81%> (+0.01%) ⬆️
SSMProblems 56.63% <ø> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant