Linear programming (LP) decoding replaces the intractable search for the most likely transmitted codeword with an optimization over a relaxed convex region, the fundamental polytope. This relaxation has a useful property: whenever it returns an integer vector, that vector is provably the maximum-likelihood codeword. It also has a known weakness. It sometimes returns a fractional corner of the region, called a pseudocodeword, which is not a codeword at all. Guessing facets proved a clean geometric asymmetry for expander codes. A true codeword sits where very many of the polytope's linear constraints hold with equality, while every pseudocodeword makes fewer of them tight, short by a constant fraction of the blocklength. The authors used this gap to motivate facet guessing: force one of the pseudocodeword's slack constraints to be tight, re-solve, and the pseudocodeword disappears. Their evidence was a gain of "up to 0.5 dB" on small synthetic codes, obtained with general-purpose LP solvers.
The codes used in practice are not expanders. These include the 5G protograph codes, the Margulis code and the Tanner code. Nobody in the record has checked whether the gap exists for them at finite length, or whether exploiting it can be cheap. This proposal does both, using one quantity that is nearly free to read off. The scalable ADMM decoder of Decomposition Methods for Large Scale LP Decoding (ADMM, the alternating direction method of multipliers, splits the problem into many small per-check projections) already computes a projection onto each check's local parity polytope. That projection reveals which local constraints are tight. We propose to measure the active-set gap from this by-product on standard codes. We then use it to drive warm-started facet guessing inside ADMM. Finally, we test directly whether the active-set signal beats the obvious cheaper signal, namely "fix the bits that came out fractional."
Core Claim
The claim has two parts, and either can fail. The first part is about measurement. On practical non-expander codes, error-floor failures of LP decoding are fractional points whose active-set deficit is still a substantial fraction of $N$. The deficit grows with blocklength when a 5G base graph is lifted to larger sizes, so the expander theorem's prediction survives qualitatively, even though its proof does not apply. The second part is about algorithms. Choosing which constraint to force tight from the pseudocodeword's inactive set eliminates failures in fewer re-solves than choosing from its fractional coordinates. With warm starts, those re-solves cost a small fraction of the initial ADMM solve. If the second part fails while the first holds, that is still a useful negative result. It would mean the gap is real but carries no information beyond integrality.
To make "active set" concrete, use Feldman's polytope: box constraints $0 \le x_i \le 1$, and for each check $j$ of degree $d_j$, one inequality per odd-sized subset of its neighbors. At a codeword every one of the $N$ box constraints is tight. For each check, exactly the $d_j$ odd-set inequalities at Hamming distance one from the local even word are tight. Hence
$$|\mathcal{A}(\mathbf{c})| = N + E \quad \text{for every codeword } \mathbf{c},$$
where $E=\sum_j d_j$ is the number of edges in the code's graph. For an ADMM output $\hat{\mathbf{x}}$ we count constraints tight to within a tolerance $\tau$ and report the normalized deficit
$$\delta(\hat{\mathbf{x}}) = \frac{N + E - |\mathcal{A}_\tau(\hat{\mathbf{x}})|}{N}.$$
The expander theorem says $\delta$ is bounded below by a constant for every pseudocodeword. We will measure its empirical distribution over actual failures.
Research Program
The first component is an instrumented ADMM LP decoder. It follows Joshi et al.'s two-slice projection, which projects onto a check's parity polytope using only the two adjacent constant-weight slices in $O(d\log d)$ time. The slice structure tells us which odd-set facets the projected local vector lies on, so active-set counting adds essentially no cost.
We validate the tolerance-based count at small $N$, where exact answers exist. For the finite-geometry codes of On the minimal pseudo-codewords of codes from finite geometries (PG(2,4) [21,11,6] and EG(2,4) [15,7,5]), that work enumerated the minimal pseudocodewords exactly with lrs, a vertex-enumeration tool. That paper never measured their active sets. We will do so, and compare the exact counts against the ADMM-estimated counts on decoded failures. This calibration step also fills a stated gap in that paper.
The second component is the measurement study. We collect high-SNR LP failures on the Margulis [2640,1320] code, the high-rate [1057,813] code, the Tanner (155,64) code, the 100-code random (3,6)-regular N=1002 ensemble from Joshi et al., and 5G base graph 2 at lifting sizes 3 and 16, as used in Learning to Decode Protograph LDPC Codes. Failures come from the additive white Gaussian noise channel and from the binary symmetric channel. For each failure we record $\delta$, the size of its fractional support, and its cost gap to the transmitted codeword. The lifting sweep supplies the finite-length scaling test.
The third component is ADMM facet guessing. When the decoder's output is fractional, we sample a small number $k$ of constraints from its inactive set. We force each one tight in turn. For a box constraint this means fixing a bit. For an odd-set constraint it means projecting that check onto the corresponding face of its local polytope, a restricted version of the same sorting-based projection. We re-run ADMM warm-started from the current primal and dual variables. Among integral candidates, we keep the one with the lowest channel cost. This is randomized facet guessing from Dimakis et al., moved into a solver that scales, with wall-clock cost measured rather than assumed.
Baselines
The naive reference point is plain ADMM LP decoding with no post-processing. Joshi et al. report that on the Margulis code it shows "no signs of an error floor down to a WER of $10^{-10}$" and trails belief propagation (BP) by about 0.4 dB in the waterfall region. Any method must improve this curve per unit of extra wall-clock time.
The strongest LP-side competitor is two-pass reweighted LP from Reweighted LP decoding for LDPC codes. After a fractional output, it solves one more LP whose objective penalizes unreliable bits. The reported BER improvement is "at least an order of magnitude" at crossover probability $p=0.11$ on the binary symmetric channel, for synthetic LDPC codes. It is the strongest competitor because it costs exactly one extra solve. We will implement it inside the same warm-started ADMM, on the same failure sets. Beating it means lower word error rate (WER) at equal mean wall-clock, or equal WER at lower cost. To compare at fixed compute, we will report our method at $k=1$, which is also a single extra solve.
The original randomized facet guessing, using an interior-point solver, is run only on the Tanner and finite-geometry codes. Its purpose is to confirm that our ADMM version matches its WER. No reported result was found on Lacuna for facet guessing on the Margulis, Tanner or 5G codes. The 0.5 dB figure applies only to small synthetic expanders.
The message-passing references are sum-product BP and normalized min-sum on the same codes. On 5G base graph 2 we also include neural min-sum, which reports gains of 0.4 dB and 0.2 dB over offset and normalized min-sum at $Z=3$, and 0.5 dB and 0.3 dB at $Z=16$. All message-passing decoders get the same maximum iteration budget as our total ADMM iterations.
The key ablations hold everything fixed except how the constraint to force is chosen. The candidates are inactive constraints (ours), fractional coordinates ranked by closeness to 1/2, low-magnitude channel LLRs, and uniformly random constraints. Each gets the same $k$ and the same warm start. Tuning budgets for $\tau$, $k$ and the ADMM penalty parameter are equalized across all ADMM variants on a held-out SNR point.
Why not just…?
Why not just use BP, which is linear-time and already near capacity? BP is better in the waterfall region, and we expect that 0.4 dB gap to persist. However, Joshi et al. show severe BP error floors on the Margulis code, where LP shows none, and BP gives no optimality certificate. We therefore target the high-SNR regime and report both regimes honestly. A natural hybrid, BP first with LP-plus-guessing only on BP failures, is included as a reported configuration rather than treated as a rival.
Why not just run reweighted LP? This is the real threat. It is cheap, and its mechanism may already be doing what the active-set argument describes. We will log $\delta$ before and after the reweighted pass. This tests whether reweighting succeeds by moving onto a larger active set, which is Gap 3 in the record. If reweighting matches facet guessing at $k=1$, we will conclude that the active-set view explains reweighting rather than replaces it, and redirect the method toward choosing the reweighting from the inactive set.
Why not just fix the fractional bits? On LP failures, fractional coordinates are exactly where box constraints are slack, so this heuristic overlaps heavily with ours. The two differ only in our method's use of the odd-set check facets. The ablation isolates that difference. If the check-facet choices add nothing, the algorithmic half of the claim is refuted, and the paper becomes a measurement study.
Why not just add redundant parity checks offline? Vontobel et al. show that complete redundant line sets give finite-geometry codes a positive pseudoweight gap. For 5G and random LDPC codes, though, redundant rows inflate check degree and constraint count, and they cannot adapt to the particular pseudocodeword that was received. We will include one comparison on the Tanner code, adding redundant rows until the per-frame cost matches ours.
Decisive Checks
Three results decide the proposal. First, on the 5G base graph 2 lifting sweep and the random N=1002 ensemble, the median $\delta$ over failures should stay bounded away from zero as $N$ grows. If it shrinks toward zero, the expander picture does not transfer. Second, at matched mean wall-clock, inactive-set guessing should achieve lower Margulis WER than both reweighted LP and fractional-bit guessing at a SNR where plain ADMM fails at about $10^{-5}$ or below. Third, warm-started re-solves should average well under one full solve. If they do not, the method's cost becomes the number of guesses times a full solve, the same kind of hidden constant that the empirical-validation literature warns about. Spielman and Teng's local clustering algorithm, for example, shipped with conservative proof-driven parameters and no experiments. We will release failure sets, active-set logs and timings so that each of the three checks can be reproduced.
References
- Guessing Facets: Polytope Structure and Improved LP Decoder
- Decomposition methods for large scale LP decoding
- On the Minimal Pseudo-Codewords of Codes from Finite Geometries
- Learning to Decode Protograph LDPC Codes
- Reweighted LP Decoding for LDPC Codes.
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning