Testing randomized algorithms: 14.5M Monte Carlo runs can miss bugs that exact tracing proves instantly

xtimv · x · 2026-11-02

Tim Vieira writes on testing randomized algorithms, using AWRS—a sampling block for SMC-based constrained generation from LLMs—as a running example:

• Monte Carlo testing (run millions of times, check output distribution) can fail: per the figure, a biased bug remains about the same size as sampling noise after 14.5M runs—'all the tests pass'
• The post presents several plausible implementations of the same algorithm (some correct, some subtly broken) and progressively stronger testing strategies, each catching a bug the previous missed
• The culminating trick: exact program tracing—enumerate every possible execution trace and check correctness exactly, proving the algorithm wrong with no sampling required
• The block is then plugged into a full SMC pipeline for end-to-end testing

Practical for anyone working on probabilistic inference, sampling algorithms, or constrained LLM generation.

Original post →

More from Research

• Fortnow revisits 3SUM, APSP and ETH: why complexity conjectures are believed — fortnow · 2026-11-02
• Why LLM steerability beats specialized models in generative bio design pipelines — chaitjo · 2026-11-02
• Epoch AI figure output growing 1.6x per year — the only 'wall' is November's zero — SamuelAlbanie · 2026-11-02
• William Hoza breaks down the BPL=L result in complexity theory — thomasahle · 2026-11-02
• YC Paper Club Hosts 'AI for Biology' Night with Cancer-Curing Teams — ycombinator · 2026-11-02
• Turing Post Curates 10 Best Papers and Videos on Agent Harness Engineering — TheTuringPost · 2026-11-02

Research channel →