Predicting and Planning the Search Cost of Shaped MIMO Detection

When a transmitter sends symbols from a standard grid (say 256-point quadrature amplitude modulation, the usual square grid of signal points) but picks low-energy points more often than high-energy ones, it gains power efficiency. This is probabilistic constellation shaping. In multi-antenna (MIMO) links, the receiver must then untangle several interfering streams. The best way to do so is a tree search called a sphere decoder, which tries symbol hypotheses one stream at a time and discards branches whose accumulated error grows too large. Recent work found that when the decoder also penalizes improbable symbols, the gains exceed the textbook 1.53 dB shaping limit, and the tree search itself visits about ten times fewer nodes Probabilistic Shaping in MIMO: Going Beyond 1.53dB AWGN Gain With the Non-Linear Demapper. That tenfold saving is only an average over simulations. The worst-case cost of sphere decoding is still exponential, the cost varies from one channel realization to the next, and nobody can yet say ahead of time how expensive a given channel and shaping choice will be.

We propose to derive a per-instance, beyond-worst-case bound on sphere-decoder search cost under shaped inputs, and then to use that bound to jointly choose two things: how much each stream is shaped, and the order in which the decoder visits streams. These two choices interact the way routing and packing do in the Traveling Thief Problem, a benchmark where the value of picking up an item depends on where in the tour it is collected. A stream's shaping level changes the search cost of every stream decoded after it, so the best order depends on the shaping and the best shaping depends on the order. In two sentences: shaping reduces tree-search cost by an amount we can bound from the prefix entropies of the decoding order, and because that cost depends on position, rate and ordering have to be optimized together rather than one after the other. We expect this to yield detectors whose throughput per unit of search effort is predictable and better than what fixed ordering heuristics give.

Core Claim

After the usual QR factorization of the channel matrix $H = QR$, the probability-aware sphere decoder explores depths $d = 1,\dots,M$ (one per stream, in a chosen order $\pi$). A partial hypothesis $s$ of length $d$ survives if its metric stays inside radius $r$. The metric is the one used by Ivanov et al., with squared residual $\|y_d - R_d s\|^2$ plus the prior penalty $-\ln P(s)$. The expected number of visited nodes is therefore a sum of survival probabilities. Bounding each indicator with a Chernoff step, with free parameter $\lambda \in (0,1)$, pulls out a factor $P(s)^{\lambda}$. Summing over hypotheses gives

$$ \mathbb{E}[N] \;\le\; \sum_{d=1}^{M} e^{\lambda r^2}\, \Big(\textstyle\prod_{j\le d} g_j(\lambda, R_{jj}, \sigma^2)\Big)\, \exp\!\Big((1-\lambda)\sum_{j \le d} H_{\lambda}(P_{\pi(j)})\Big), $$

In this bound, $H_\lambda(P)$ is the Rényi entropy of order $\lambda$ of the stream's symbol distribution. The factor $g_j$ is the Gaussian moment term, which depends on the $j$-th diagonal entry $R_{jj}$ of the triangular factor and the noise variance $\sigma^2$. Uniform inputs make every $H_\lambda$ equal to $\log|\mathcal{X}|$, which recovers the familiar exponential growth. Shaping lowers the Rényi entropies. Placing strongly shaped streams early in the order lowers every later prefix sum, and this is where the coupling comes from.

The analytical claim has two parts. First, under a smoothed channel model $H = H_0 + \tau G$, where $H_0$ is an arbitrary adversarial matrix and $G$ is i.i.d. Gaussian, the expectation of this bound over $G$ is controlled by $\tau$ and the prefix entropies rather than by the worst-case $H_0$. Second, highly correlated channels, where some $R_{jj}$ are pinned near zero by structure, remain hard even under smoothing. This mirrors the fragile-versus-robust split that Smoothed Performance Guarantees for Local Search proved for scheduling: random noise removes the dependence on the machine count for unrestricted machines, but not when assignment constraints are structural. That paper supplies our template. It perturbs scalar job sizes, and we perturb channel matrices whose structure (correlation) plays the role of the restricted-machine constraints.

Research Program

The first strand is analysis. We will tighten the bound above by optimizing $\lambda$ per depth. We will prove the smoothed statement for i.i.d. and Kronecker-correlated channel families. We will also identify the correlation regimes in which the exponential dependence survives smoothing. The output is also an instance-specific certificate: for each channel realization, a cheap-to-compute upper bound on expected nodes that can be checked against the measured count. This follows the spirit of Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut, which replaces universal worst-case ratios with per-instance dual certificates. Its known weakness is loose certificates when the relaxation gap is wide, and our analogue of that failure is looseness at low SNR, which we will measure rather than assume away.

The second strand is the coupled optimization. For each channel realization, we choose an order $\pi$ and a shaping level for each stream from a small menu of Maxwell–Boltzmann distributions produced by constant composition distribution matching (a pre-encoder that turns uniform bits into sequences with a fixed symbol histogram). The objective is achievable sum rate minus a price on the certified search cost, or equivalently maximum rate under a node budget. The structure is the one the Traveling Thief Problem made canonical. Decisions accumulate: in the thief problem, knapsack weight slows travel; here, prefix entropy inflates later search. Exact Approaches for the Travelling Thief Problem solved small instances exactly by dynamic programming over visited subsets and showed that decoupled two-stage solving leaves large gaps. We borrow both lessons. Dynamic programming over subsets of streams is trivially cheap for $M \le 8$, so we get exact optima to measure heuristics against. That paper's decoupled-versus-joint comparison becomes our central ablation. For larger arrays, where subset dynamic programming stops being cheap, we fall back to local search over orderings with the certificate as the evaluation function.

Baselines

The naive reference point is uniform 256QAM with a sphere decoder using standard SNR-sorted ordering. Ivanov et al. report that probability-aware sphere decoding with CCDM Maxwell–Boltzmann shaping gains over 2 dB (low correlation) and 3.5 dB (medium correlation) in SNR over this reference, with roughly 10x fewer visited nodes in low correlation. We will reproduce that setting first. We are not trying to beat the error-rate figures; our target is throughput at matched search effort.

The strongest existing method is that Ivanov et al. configuration itself: a single shaping level on all streams, with the decoder ordering chosen independently of the shaping. It is the strongest competitor because it already captures the non-linear demapping gain. We will run it on the identical TDL-C channels, LDPC code, SNR grid, and node-budget caps. Beating it means either higher goodput at the same 95th-percentile node count, or the same goodput at a lower tail node count.

The ablation that isolates our key ingredient is a decoupled two-stage version. It first chooses per-stream shaping levels to maximize rate given the channel, then applies the usual SNR-sorted ordering. This is the analogue of the S1 heuristic in the thief-problem literature, which averaged a 38.9% gap from optimum in Exact Approaches for the Travelling Thief Problem. A second ablation uses the joint optimizer but replaces our bound with the Shannon entropy of each prefix, which tests whether the Rényi order matters. Linear MMSE detection with shaping is also reported. Ivanov et al. show it reverts to AWGN-like 1.53 dB gains, so it bounds what can be had without tree search.

Why not just…?

Why not just use a fixed-complexity K-best detector with the prior-aware metric? A K-best detector keeps only the best K partial hypotheses at each depth. It fixes cost by construction and removes the variability problem, so it is a real threat. It does not remove the coupling, though. Which streams go first still decides whether the true path survives truncation, and K is a budget that has to be spent somewhere. We will run prior-aware K-best at K values matched to our node budgets, with and without our ordering and shaping choices. If K-best with default ordering matches our method at equal complexity, the joint-planning claim fails and only the analytical explanation survives.

Why not just measure complexity offline per correlation profile and store a lookup table? For a 4x4 link, 24 orderings times a handful of shaping levels is easy to simulate offline per 3GPP correlation profile. The certificate earns its place only if channel-to-channel variation within a profile is large enough that per-realization choices beat per-profile choices. We will measure exactly that gap. If it is small, we will report that the bound is explanatory rather than operational.

Why not just learn the allocation with reinforcement learning? Data-Driven Optimization of Directed Information over Discrete Alphabets shows that input distributions can be learned by policy gradient when no model is available. Here, however, a closed-form cost surrogate exists, and learning would have to rediscover the prefix structure from sampled node counts. We will train a policy-gradient allocator on the same reward with a matched simulation budget and compare its gap to the exact dynamic-programming optimum.

Why not just decode with MMSE and avoid tree search? Ivanov et al. report that MMSE gives back the extra gain, which returns to the 1.53 dB regime. MMSE therefore serves as a floor, not a competitor.

Proposed Experiments

All experiments use the 3GPP TDL-C setup from Ivanov et al.: 4x4 MIMO, 256QAM, 5G NR LDPC, 300 ns delay spread, 11 Hz Doppler, and low and medium correlation profiles. We extend it to 8x8 to stress ordering. The first check is certificate tightness: for each realization, the ratio of certified to measured expected nodes, as a function of SNR and correlation. The prediction is tight bounds at moderate and high SNR in low correlation, and systematic looseness in medium correlation, in line with the robust-structure hypothesis. The second check is the smoothed claim: sweep $\tau$ around adversarial ill-conditioned $H_0$ and test whether tail complexity falls with $\tau$ as the bound predicts. The third check, and the decisive one, compares joint versus decoupled versus fixed-shaping configurations. For each, we plot goodput against 95th-percentile node count, with the exact dynamic-programming optimum as ground truth for the gap of each heuristic. The proposal succeeds if joint planning closes a measurable share of the gap between the decoupled scheme and the exact optimum, and if prior-aware K-best at matched complexity does not already reach the same curve. Neither the TTP exact study nor Ivanov et al. reports a joint rate-ordering result for MIMO, so no reported result was found on Lacuna for this comparison, and the reproduced Ivanov configuration will serve as the reference.