Recovering the symbols sent by many users to a large antenna array is, in its exact form, a search over exponentially many candidate symbol vectors. Practical receivers therefore run fast approximations: linear filters, loopy message passing, or learned neural detectors. None of these can tell the receiver, for a given channel use, whether its answer is the true maximum-likelihood one. This note proposes a detector that can. It rewrites detection as minimizing an energy over a graph with one node per symbol and one edge per pair of interfering users. It then runs a dual coordinate-descent method, which keeps a provable lower bound on the best achievable energy and improves that bound by updating whole spanning trees of the graph at once. A small graph neural network (GNN, a network that computes on nodes by exchanging messages along edges) decides which tree to update next. The GNN affects only how fast the bound tightens. It cannot affect whether the bound is valid. Whenever the energy of the decoded answer equals the bound, the receiver has a certificate that the answer is exactly optimal.
The opportunity matters because two families of existing methods trade away something the other keeps. Pruned message passing and edge-dropping GNNs make dense detection graphs cheap by discarding couplings heuristically, and they come with no guarantee. Dual tree-block methods from the graphical-models literature come with guarantees but have never been engineered or scheduled for dense, ill-conditioned wireless channels. The proposal keeps every coupling in the objective and prunes only the work schedule. It also measures something no cited paper reports: on realistic correlated channels, what fraction of channel uses can be certified optimal within a fixed computation budget?
Core Claim
Write the real-valued model $y = Hx + w$, where $x \in \mathcal{A}^{2K}$ holds the real and imaginary parts of $K$ users' symbols. Each coordinate takes values in a pulse-amplitude alphabet $\mathcal{A}$: four levels for 16-QAM, sixteen for 256-QAM. Maximum-likelihood detection is then the problem of minimizing a pairwise energy
$$E(x) = \sum_i \left(G_{ii}x_i^2 - 2z_i x_i\right) + \sum_{i<j} 2G_{ij}\,x_i x_j,$$
where $G = H^\top H$ is the Gram matrix and $z = H^\top y$ is the matched-filter output. This is a fully connected pairwise Markov random field (a probabilistic graphical model whose terms involve at most two variables each). Its natural bipartite representation has symbol variables on one side and pairwise coupling factors on the other.
Tree Block Coordinate Descent for MAP in Graphical Models unifies max-sum diffusion, TRW-S and MPLP under one dual objective $J(f)$, a lower bound on $\min_x E(x)$. It shows that exact updates on entire spanning trees decrease this objective monotonically, and that a MAP answer can be decoded when the underlying linear-programming relaxation is tight and the optimum is unique. Hence for any decoded $\hat x$ the gap
$$\Delta = E(\hat x) - J(f) \;\ge\; 0$$
is an anytime, per-instance certificate: $\Delta = 0$ proves $\hat x$ is the maximum-likelihood vector, and $\Delta > 0$ bounds its log-likelihood suboptimality.
We claim three things. First, a learned policy that picks which spanning tree to update, given the current dual state on the bipartite graph, closes $\Delta$ in substantially fewer multiplications than fixed sweep orders. Second, under a coherence-block budget, this certifies a useful fraction of channel uses on correlated millimeter-wave channels. Third, the uncertified remainder is exactly where a small exact search should be spent. The learned component can make the detector slow, but never wrong-without-warning.
Relation to Prior Work
Three works motivate the gap by pruning dense detection graphs heuristically. Belief-Selective Propagation Detection for MIMO Systems truncates each message to its most likely symbols and simplifies most edges with a max-log approximation. It reports a 4 dB gain over plain belief propagation at BER $10^{-4}$ and comes within 0.2 dB of the sphere decoder on $8\times4$ 16-QAM, but it uses fixed thresholds and has no convergence or optimality guarantee. Edge Graph Neural Networks for Massive MIMO Detection drops low-correlation edges by an empirical threshold that its authors leave to future tuning. Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm is closer in spirit because it bounds the approximation ratio. However, it keeps a single maximum spanning tree and discards the remaining edges permanently. That is a poor fit for dense Gram matrices, where many couplings are non-negligible. Our method differs from all three: every edge stays in the objective, and different trees are visited over time.
Two works supply the method. The tree-block dual framework above provides monotonicity and decodability. Message Passing for Max-weight Independent Set shows that max-product fixed points are correct exactly when the linear-programming relaxation has no integrality gap, and gives a barrier-based dual descent that converges on any graph. It serves as a second certified solver we compare against.
Two works constrain the design. On Representing Mixed-Integer Linear Programs by Graph Neural Networks proves that bipartite GNNs cannot separate instances with symmetric structure, and that random node features restore separation. For us, symmetric users make the scheduling GNN assign them identical scores. This does not break correctness, but it can stall progress, so random features are a tested ingredient rather than an assumption. Near-symmetric users also tend to create near-ties in the energy, which violates the uniqueness condition for decodability. The certificate should then honestly fail, and we measure how often it does. Accelerated consensus via Min-Sum Splitting proves accelerated convergence on loopy graphs, but only for quadratic averaging and only with knowledge of a global eigenvalue. We take it as evidence that ordering and memory matter, not as a usable guarantee for discrete detection.
Neural detectors without certificates frame the competition. Graph Neural Network Enhanced Approximate Message Passing for MIMO Detection unrolls approximate message passing with a user-graph GNN refiner. It is efficient at scale, but its theory assumes i.i.d. channels. RE-MIMO uses permutation-equivariant attention and is robust to correlation, at quadratic per-step cost. Primal-Dual Neural Algorithmic Reasoning aligns bipartite GNN messages with primal-dual steps but explicitly offers no worst-case guarantee. Our design differs from these three in the same way: the network never produces the answer, it only orders the steps of a solver whose answer is checkable.
Research Program
The first component is the solver. It is a real-valued tree-block dual descent on the fully connected symbol graph. Each update solves one spanning tree exactly in $O(K|\mathcal{A}|^2)$ by a two-pass sweep, and the solver is warm-started from a linear minimum-mean-square-error estimate, as belief-selective propagation does. We will also add symbol truncation inside the dual: only the top candidates per node are enumerated during a tree pass, while every label stays in the objective so the bound remains valid. This makes 64- and 256-QAM tractable without the soundness loss of pruning messages outright.
The second component is the scheduler. It is a bipartite GNN over variable and coupling-factor nodes. Node features are the current reparameterized unary costs and the max-marginal disagreement between neighbors. Edge features are $G_{ij}$ and the local dual residual. A tree is formed by a maximum-weight spanning tree over the GNN's edge scores, so the network's output is always a legal block. The scheduler is trained with the per-step decrease in $\Delta$ per multiplication as the reward, and it is trained on small user counts and tested on larger ones, exploiting size-independence.
The third component is the budget policy. When the coherence budget runs out with $\Delta > 0$, a bounded depth-first search is run over only the nodes whose max-marginals are not yet decisive. The current dual bound is used for pruning. The analysis will characterize empirically which channel properties predict certification: condition number, line-of-sight strength, and user loading.
Baselines
The naive reference point is a linear minimum-mean-square-error detector. It is cheap to describe, requires a cubic-cost inverse, and is reported by the GBCD ASIC paper to trail coordinate descent by 4 dB to 10 dB SNR in $16\times16$ QuaDRiGa loading. We run it on identical channel draws. Beating it is necessary but uninteresting.
The strongest existing accuracy competitor on i.i.d. channels is belief-selective propagation from Belief-Selective Propagation Detection for MIMO Systems, which reports performance within 0.2 dB of the sphere decoder on $8\times4$ 16-QAM. We reimplement it with its minimum-mean-square-error initialization and tune its two truncation thresholds on the same validation grid we use for our own budget. Beating it means matching its BER within 0.2 dB at equal real-multiplication count, while additionally certifying a nonzero fraction of channel uses. On correlated channels, beating it means lower BER at equal cost.
The strongest competitor on realistic channels is the Gram-domain block coordinate descent detector of the same ASIC paper. It is simulated in floating point with its SINR ordering and with unfolded denoisers retrained on our data. We add the RE-MIMO detector as the strongest learned competitor under correlation, trained on identical data with a matched hyperparameter budget. No reported QuaDRiGa BER value for the GBCD detector beyond the 4–10 dB margin over linear detection is available in the file, and no reported QuaDRiGa result was found on Lacuna for belief-selective propagation or RE-MIMO. We will therefore generate all of these numbers ourselves.
Exact reference points come from the sphere decoder, which is used for ground truth and for measuring gap-to-optimal. The key ablation is the identical dual solver run with a fixed TRW-S-style sweep order and with random tree selection. This isolates what learning buys. A second ablation removes random features from the scheduler.
Why not just…?
Why not just run TRW-S or MPLP with a fixed schedule? This is the real threat. If fixed sweeps certify as many instances per multiplication as the learned scheduler, the GNN adds nothing. The fixed-schedule ablation at matched multiplication counts settles it. If the learned gain is under roughly 1.5× in multiplications-to-certificate, we will drop the learning component and report the certified fixed-order detector as the contribution. That detector would still be new for correlated MIMO.
Why not just use belief-selective propagation or damped loopy propagation? They can be accurate on i.i.d. channels. However, Belief-Selective Propagation Detection for MIMO Systems relies on hand-set truncation and has no proof that pruning preserves the correct answer, and plain propagation shows cycle-induced error floors in the same paper. Neither yields a per-instance optimality statement. We compare BER directly, and we report how often each silently returns a non-ML answer, which our gap exposes.
Why not just use an end-to-end neural detector like RE-MIMO or AMP-GNN? They may match our BER, and on i.i.d. channels AMP-GNN is far cheaper at 1024 users. They cannot, however, flag their own failures, and AMP's theory breaks under correlation. If they dominate on both BER and cost, our contribution narrows to certification alone. We will state that plainly and measure what certification is worth, for example by passing certified symbols as hard decisions to a downstream decoder.
Why not just use the sphere decoder? Its worst-case cost is exponential, which is why hardware work avoids it. Our fallback reuses its search but restricts it to uncertified coordinates with a dual-bound radius, so we measure how much of its cost the dual phase removes.
Proposed Experiments
We run on synthetic i.i.d. Rayleigh channels at $8\times4$ and $16\times8$ with 16- and 64-QAM, matching Belief-Selective Propagation Detection for MIMO Systems, and at $32\times16$ with 16-QAM, near the EGNN setting. We also run on QuaDRiGa mmMAGIC 60 GHz urban-microcell channels with 128 antennas and 16 users, in both line-of-sight and non-line-of-sight conditions, up to 256-QAM, matching the GBCD ASIC paper.
The metrics are BER and SER against SNR, gap to the sphere decoder, and the certified fraction, meaning the share of channel uses with $\Delta = 0$ as a function of real multiplications. We also report the anytime curve of $\Delta$ and the fallback search size.
The decisive checks are three. First, is the certified fraction on QuaDRiGa line-of-sight channels at moderate SNR large enough to matter? The claim is falsified if it stays near zero at budgets comparable to linear detection. Second, does the learned scheduler beat the fixed and random schedules at matched multiplications? Third, in a constructed stress test with users sharing near-identical angles of arrival, do random features restore scheduler progress, and does the certificate correctly refuse to certify near-tied instances rather than certifying wrong ones?
References
- Tree Block Coordinate Descent for MAP in Graphical Models
- Belief-selective Propagation Detection for MIMO Systems
- Edge Graph Neural Networks for Massive MIMO Detection
- Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm
- Message Passing for Max-weight Independent Set
- On Representing Mixed-Integer Linear Programs by Graph Neural Networks
- Accelerated consensus via Min-Sum Splitting
- GNN-Enhanced Approximate Message Passing for Massive/Ultra-Massive MIMO Detection
- RE-MIMO: Recurrent and Permutation Equivariant Neural MIMO Detection
- Primal-Dual Neural Algorithmic Reasoning
- A Deep-Unfolding-Optimized Coordinate-Descent Data-Detector ASIC for mmWave Massive MIMO