BP Decoder Performance: Fundamental Architecture Issues

[GiggleLiu]

Problem Summary

The current BP decoder implementation shows only 2% improvement over a simple syndrome-parity baseline decoder, which is far below expected performance based on published research. After analyzing the code and comparing against recent literature, I've identified fundamental architectural issues that prevent the decoder from working properly.

Expected vs. Actual Performance

What We Should See (from Literature)

Based on recent 2024 research on BP decoders for surface codes:

• Error thresholds: 14-17% for modern BP variants (Improved BP Decoding, arXiv:2407.11523)
• Planar surface code threshold: ~10% for standard BP (Surface Code Error Correction)
• Circuit-level noise threshold: ~1% for MWPM, higher for BP (PyMatching decoder)
• At p=0.03 (3% physical error rate): Should achieve logical error rate well below 3% for d=3+ codes

What We Actually See

At p=0.03 (3% physical error):

Decoder	LER	Precision	Recall	F1
Syndrome-parity baseline	50.6%	35.6%	50.8%	0.418
BP Decoder	49.6%	36.1%	50.3%	0.421
Improvement	2.0%	-	-	-

This is broken! At 3% physical error, we're getting ~50% logical error rate, which means the decoder is barely better than random guessing.

Root Cause Analysis

I've identified three fundamental architectural issues:

Issue 1: Wrong Factor Graph Structure

Current UAI Model (from dem_to_uai()):

# Lines 174-182 in dem.py
n_detectors = dem.num_detectors  # 24 for d=3
lines.append(str(n_detectors))    # Variables = DETECTORS
lines.append(str(len(errors)))    # Factors = ERROR MECHANISMS

This creates:

• Variables = Detectors (binary: fired=1, not fired=0)
• Factors = Error mechanisms (one factor per DEM error)

The Problem:

• This models P(detectors | errors), the forward model
• For decoding, we need P(errors | syndrome), the inverse model
• Setting detectors as "evidence" makes no sense—we already KNOW the detector states from the syndrome!

Issue 2: Inference on the Wrong Quantity

What the code does:

# examples/tanner_graph_walkthrough.py, line 438
evidence = {det_idx + 1: int(syndrome[det_idx]) for det_idx in range(len(syndrome))}
bp_ev = apply_evidence(bp, evidence)
state, info = belief_propagate(bp_ev, ...)
marginals = compute_marginals(state, bp_ev)  # Marginals over DETECTORS!

The Problem:

• After setting evidence, BP computes marginals over detector variables
• But we already know the detector values (from the syndrome)!
• What we don't know is which errors occurred
• The marginals over detectors are useless for decoding

Issue 3: Decoding Logic Outside BP

Current approach:

# Lines 457-499 in examples/tanner_graph_walkthrough.py  
# Build error likelihood scores based on syndrome
for det_idx in syndrome_active:
    errors_for_detector = np.where(H[det_idx, :] == 1)[0]
    error_likelihoods[errors_for_detector] *= 2.0  # Ad-hoc boost
    
# Apply parity heuristic
if syndrome_weight % 2 == 1:
    flip_likelihood_avg *= 3.0  # Ad-hoc multiplier

The Problem:

• The "decoding" happens outside BP using ad-hoc heuristics
• This completely bypasses the power of belief propagation!
• The 2% improvement comes from these heuristics, not from BP
• It's essentially a fancy wrapper around syndrome-parity decoding

What a Proper BP Decoder Should Do

A correct BP decoder for surface codes should:

1. Correct Factor Graph

Variables = Error mechanisms (binary: occurred=1, didn't occur=0)
Factors = Parity check constraints (one per detector)
Evidence = Observed syndrome s

2. Proper Inference

• Enforce syndrome constraints: s_i = ⊕_{j: H[i,j]=1} e_j (parity checks)
• Run BP to compute marginal probabilities over errors
• Decode by finding most likely error configuration

3. Maximum Likelihood Decoding

error_config = argmax P(e | s) 
             = argmax P(s | e) · P(e)  [Bayes' rule]
             = argmax [∏_i δ(s_i = ⊕_j H[i,j]e_j)] · [∏_j p_j^{e_j}(1-p_j)^{1-e_j}]

Proposed Solutions

Option 1: Build Correct Factor Graph

Rewrite dem_to_uai() to create:

• Variables: Error mechanisms (286 binary variables for d=3, r=3)
• Factors: Parity constraints (24 factors, one per detector)
• Each factor enforces: detector_i = XOR(errors affecting detector i)

Option 2: Use Existing Tools

Consider using proven implementations:

• PyMatching (GitHub) - MWPM decoder, ~1% threshold
• LDPC (bp_osd) - BP+OSD implementation
• Stim built-in decoders for benchmarking

Option 3: Implement Modern BP Variants

From the 2024 literature:

• EWAInit-BP: Adaptive prior probability updates
• MBP: Momentum-based belief propagation
• BlockBP: Outperforms MWPM by >10x in some regimes

Impact

This affects:

• ❌ Tanner Graph Walkthrough tutorial (PR Add Tanner Graph Walkthrough Tutorial with Logical Error Rate Analysis #37) - shows misleading "2% improvement"
• ❌ Any users trying to use pytorch_bp module for actual decoding
• ❌ Credibility of the package - claims "BP decoding" but doesn't actually work

References

1. Improved Belief Propagation Decoding on Surface Codes (2024)
2. Quantum Error Correction Below the Surface Code Threshold
3. Error Correction Zoo: Surface Code
4. PyMatching: MWPM Decoder
5. BP-OSD Decoder

Next Steps

I propose:

1. Document this issue (this issue)
2. Add warning to current tutorial about performance limitations
3. Design correct factor graph structure
4. Implement proper BP decoder
5. Benchmark against PyMatching to validate

Should I proceed with designing the corrected architecture?

---

Labels: bug, enhancement, research, decoder
Priority: High - affects core functionality

[GiggleLiu]

Critical Update: Decoders Are Making Things WORSE

I did a deeper analysis based on the observation that the baseline LER seems too high, and found an even more serious problem:

The Real Numbers (p=0.03, d=3, r=3)

Approach	LER	Status
No decoding (natural errors)	35.4%	Baseline
Syndrome-parity decoder	49.9%	❌ WORSE (+14.5%)
BP decoder	49.6%	❌ WORSE (+14.2%)
Random guessing	~50%	❌ WORSE

Key Finding: Both decoders make things WORSE, not better!

The "2% improvement" I reported earlier was comparing two broken decoders (49.6% vs 50.6%). Both are significantly worse than doing nothing (35.4%).

Why Syndrome Parity Fails

Syndrome parity (predict flip if syndrome weight is odd) only works if there's correlation:

Logical flip rate | even syndrome: 35.2%
Logical flip rate | odd syndrome:  35.6%

There's NO correlation! Syndrome parity is essentially random for surface codes, which is why it gives ~50% error rate.

Why This Confirms the Architectural Issues

This confirms Issues #1-3 in my original post:

1. The UAI factor graph has the wrong structure (detectors as variables)
2. We're inferring the wrong quantity (detector marginals instead of error marginals)
3. The "decoding" heuristics are fundamentally broken

A proper decoder should:

• Reduce LER from 35.4% to <10% (targeting the threshold)
• Use the syndrome to identify and correct errors
• NOT make random-like predictions

Impact

This is more severe than initially reported:

• The tutorial (PR Add Tanner Graph Walkthrough Tutorial with Logical Error Rate Analysis #37) shows "2% improvement" but both decoders increase errors by ~14%
• Users following the tutorial will build worse-than-useless decoders
• This needs urgent correction

I recommend:

1. Add prominent WARNING to PR Add Tanner Graph Walkthrough Tutorial with Logical Error Rate Analysis #37 about decoder being non-functional
2. Either fix the architecture or remove decoder evaluation entirely
3. Benchmark against known-good decoder (PyMatching) to validate any fixes

[ChanceSiyuan]

OSD Investigation Confirms Architecture Issues

I've implemented and tested an OSD (Ordered Statistics Decoding) post-processor to investigate the BP decoder performance. The results strongly support the architecture issues described in this issue.

OSD Test Results

Decoder	Logical Error Rate
BP only	0.193
BP + OSD-0	0.375
BP + OSD-10	0.314

OSD makes performance WORSE, not better. This is a strong indicator that the soft information from BP is not meaningful.

Why This Confirms the Architecture Problem

In a properly functioning BP decoder:

1. BP provides marginal probabilities P(error_i = 1 | syndrome)
2. OSD uses these probabilities to sort variables by reliability
3. OSD searches over the most uncertain variables to find minimum-weight solutions
4. Result: OSD should improve upon BP's hard decisions

What we observe:

1. OSD solutions satisfy the syndrome constraint (verified)
2. But OSD solutions have HIGHER logical error rate than BP
3. This means the "soft information" from BP is misleading OSD

Interpretation

The BP marginals are not representing true error probabilities. As noted in this issue:

• The current factor graph has Variables = Detectors instead of Variables = Errors
• BP computes marginals over detectors (which we already know from the syndrome)
• The "error probabilities" extracted from this are not meaningful

OSD is correctly finding minimum-weight solutions that satisfy the syndrome, but it's being guided by incorrect probability information, leading to worse performance.

Recommendation

The OSD implementation is ready (branch: fix/osd-decoder-improvements), but it cannot be properly evaluated until the factor graph architecture is corrected per this issue. Once BP provides true error marginals, OSD should provide the expected performance improvement.

See also: Comment on Issue #6 for full OSD implementation details.

[ChanceSiyuan]

Note: BP+OSD Fix (Related but Separate Issue)

The recent fix on fix/osd-decoder-improvements branch addresses a different issue - the OSD post-processing module was using Hamming weight instead of soft-weighted cost.

What was fixed:

• src/bpdecoderplus/osd.py - OSD now uses LLR-based soft-weighted cost
• Results: BP+OSD-15 achieves 6.8% LER vs 10.9% for BP-only (37.6% improvement)

What this issue describes (still open):

• The fundamental BP architecture using UAI factor graphs (pytorch_bp/)
• The factor graph structure inverts the inference direction
• This is a deeper architectural issue separate from OSD

The OSD fix helps when using BatchBPDecoder + OSDDecoder (which directly uses the parity check matrix H), but doesn't address the UAI-based BP in pytorch_bp/belief_propagation.py.

See docs/bp_osd_fix.md for details on the OSD fix.