Decoy Pilots: False-Discovery Control for Asynchronous Massive Random Access

When thousands of cheap sensors share one uplink and none of them synchronize their clocks, the base station has to work out from a single noisy received block which devices are transmitting, with what delay, and over what channel. The strongest current receivers use robust message passing, iterative estimators built to stay stable when the measurement matrix is far from random. Even these receivers end with an arbitrary step: a hand-tuned amplitude threshold decides which devices count as "active." The authors of the best asynchronous detectors name automatic, reliable setting of this threshold as an open problem (Bian et al., 2023). A threshold that is slightly off either floods the scheduler with phantom users or silently drops real ones.

We propose to calibrate the threshold inside each received frame by planting decoys. Decoys are extra pilot sequences, the known signatures that identify each device, that the receiver adds to its dictionary but that are never assigned to any device. Decoys never transmit, so the scores the receiver gives them show exactly how high a silent device can score in this frame, at this noise level, with this interference. Comparing each real device's score with the decoy scores gives a distribution-free p-value. A false-discovery-controlling rule turned into a selective decision then splits devices three ways: devices declared active under a strict error budget, devices deferred to a cheap confirmation round, and devices rejected. The receiver needs no labeled calibration data, no clean test set, and no assumption that the channel statistics match a simulator.

Core Claim

The claim has two parts and keeps them apart. Validity comes from the decoys. Suppose decoy pilots are drawn from the same distribution as real pilots and given the same set of candidate delays. Suppose also that the estimator treats dictionary columns symmetrically, meaning that permuting the users simply permutes the outputs. Then, conditional on which devices are active, the scores of inactive devices and of decoys are exchangeable. Power comes from the estimator. Robust message passing produces much better separation between active and silent scores on delay-distorted pilot matrices than standard approximate message passing or convex solvers. So the same decoy calibration admits far more true users at the same false-discovery rate.

Concretely, let $s_j$ be the activity score of real device $j$ (the energy of its recovered channel, summed over antennas and candidate delays), let $\tilde s_1,\dots,\tilde s_m$ be the scores of $m$ decoys, and let $N$ be the number of real devices. The conformal p-value is

$$p_j = \frac{1 + \#\{i : \tilde s_i \ge s_j\}}{m+1},$$

and the receiver declares active every device whose score exceeds the smallest threshold $t$ satisfying

$$\widehat{\mathrm{FDP}}(t) = \frac{N}{m}\cdot\frac{1 + \#\{i : \tilde s_i \ge t\}}{\max(1, \#\{j : s_j \ge t\})} \le \alpha,$$

where $\alpha$ is the target false-discovery rate, the expected fraction of declared-active devices that are actually silent. This is the Benjamini–Hochberg procedure applied to the p-values above, or equivalently a target-decoy counting rule. Note that the factor $N/m$ assumes in the worst case that every real device is silent. One consequence is that $m$ sets the resolution: p-values cannot go below $1/(m+1)$. The budget therefore cannot be tighter than roughly $N/(m\cdot\#\text{declared})$, which tells us how many decoys we need.

The distance from prior work is concrete. Asynchronous detectors such as OAMP/MAMP (Bian et al., 2023), free-probability AMP (Bian et al., 2024), and unfolded learned AMP (Deep-Learned AMP for Asynchronous Massive Connectivity) produce hard decisions from fixed thresholds and carry no error guarantee. Conformal Labeling (Selective Labeling with False Discovery Rate Control) and STRATCP (Act or Defer) supply the FDR-controlled act-or-defer logic we reuse. Both need a labeled, exchangeable calibration set, which the base station does not have: it never sees ground-truth activity, and the channel drifts frame to frame. Decoys replace that labeled set with synthetic nulls generated inside each frame. The AMP-based full conformal work of Clarté and Zdeborová builds leave-one-out regression intervals from standard AMP. It differs from our work in task (regression intervals rather than multi-user detection) and in mechanism, and the authors report convergence failure under strongly structured matrices, which is exactly the regime asynchrony creates. Conformal methods for wireless (Calibrating AI Models for Wireless Communications; Conformal-AMC) handle single links with labeled or online feedback and do not address unknown multi-user activity.

Research Program

The first task is the validity argument and where it breaks. We will state and prove the exchangeability condition for estimators that are equivariant to permuting groups of columns. The OAMP linear step is a function of the whole matrix and permutes with it. Its per-user denoiser is separable, and free-probability AMP has the same structure. So these estimators should qualify exactly at any finite size, not only asymptotically. Deep-unfolded AMP qualifies only if its learned parameters are shared across users. Three things can break the condition, and we will treat each one. First, if real pilots come from a structured family such as Zadoff–Chu sequences, decoys must be drawn from the same family under the same rule. Second, if path loss is modeled per device, decoys inherit no path loss, because silent devices have no channel. Third, a denoiser with user-specific priors breaks symmetry, so priors must be applied identically to decoys or dropped. Whether Benjamini–Hochberg remains valid under the joint dependence the shared estimator induces is a genuine theoretical question. If we cannot prove it, we fall back to the counting rule above with its "+1" correction, which is conservative under exchangeability of the full null set.

The second task is the cost of decoys. Adding $m$ dictionary groups does not change the pilot length or the number of transmitters. It does widen the matrix, which can move the detection phase transition and adds roughly $m/N$ relative compute to free-probability AMP. We will measure detection power as a function of $m/N$ and pick the smallest $m$ that achieves the target $\alpha$ resolution.

The third task is the selective layer. Following STRATCP's action and deferral arms, devices passing a strict budget $\alpha_{\text{act}}$ are scheduled immediately. Devices passing only a looser $\alpha_{\text{def}}$ are sent a short confirmation request. Everything else is ignored. The deferral arm is what turns a guarantee into usable throughput: it converts borderline devices into a bounded number of cheap retransmissions rather than silent drops.

The fourth task is power. We will run the same decoy calibration on top of several estimators to show how much robust message passing contributes.

Baselines

The naive reference point is the fixed-threshold receiver used in the source papers. This is free-probability AMP with the activity threshold tuned once on simulated frames at a nominal SNR and user count, then frozen. We will run it on identical frames and report its realized false-discovery rate when noise power, path-loss spread, and the active-user count move away from the tuning point. Beating it means our realized FDR stays at or below $\alpha$ across all such shifts while the frozen threshold drifts above it.

The strongest existing detector is free-probability AMP (Bian et al., 2024). It reports supporting 76% more active users than standard AMP at false alarm $10^{-1}$ and missed detection $2\times10^{-3}$, in the 400-user, 16-antenna asynchronous setup. OAMP/MAMP (Bian et al., 2023) reports 4.31 s versus 6.94 s runtime for MAMP versus OAMP in the same setup. No reported false-discovery-rate result was found on Lacuna for any asynchronous activity detector. For a fair comparison, we give free-probability AMP an oracle threshold, re-tuned per test condition on 1,000 labeled frames from that exact condition, with the same iteration count and pilot length as our system. Beating it means matching its missed-detection rate at equal realized FDR without any labeled frames, and holding the FDR guarantee where the oracle threshold cannot be re-tuned.

The strongest calibrated competitor is split-conformal Conformal Labeling (Selective Labeling with False Discovery Rate Control). It builds p-values from a labeled calibration pool of silent-device scores collected from simulated frames, using the same free-probability AMP scores. It receives the same calibration-pool size as our total decoy count across frames. Beating it means equal power when the simulator matches deployment, and preserved FDR when it does not.

The key ablation swaps the estimator under fixed decoy calibration: free-probability AMP, OAMP, damped standard AMP, and Group LASSO. This isolates how much power robust message passing contributes. A second ablation removes the deferral arm, which isolates its throughput effect.

Why not just…?

Why not just set the threshold from state evolution? Robust message passing comes with state evolution, a deterministic recursion that predicts the effective noise variance on each recovered coefficient. A Gaussian tail with that variance gives a parametric p-value at no extra cost, and this is a real threat. Its weakness is that state evolution is an asymptotic statement about large rotation-invariant matrices. Here the setting has 400 devices, a delay-structured pilot matrix, and per-device path loss, so the activity score is a sum over antennas and delays whose null distribution is not the textbook one. We will run state-evolution p-values with Benjamini–Hochberg on the same frames and report realized FDR against $\alpha$. If it holds within sampling error across all conditions, decoys add little, and we will say so and recommend the cheaper method.

Why not just calibrate offline on simulated frames with known activity? This is split conformal with labels. It works exactly when deployment matches the simulator, and it is the comparison point in the Baselines section. The evidence against relying on it is indirect but consistent. Conformal guarantees break when calibration and test data stop being exchangeable, as the wireless conformal work documents for drifting channels (Calibrating AI Models for Wireless Communications; Conformal-AMC). A base station also never observes ground-truth activity, so it cannot refresh labels online. Decoys calibrate inside the frame under whatever conditions that frame has. The shift experiments below decide the matter.

Why not just add decoys to Group LASSO or plain AMP and skip robust message passing? The validity argument applies to any column-symmetric estimator, so this alternative is legitimate for validity. The question is power. Group LASSO already shows higher error than OAMP/MAMP on this problem (Bian et al., 2023), and standard AMP degrades badly under delays (Bian et al., 2024). Poor separation between active and silent scores means fewer discoveries at a fixed $\alpha$. The estimator ablation measures this gap directly. If it turns out small, the contribution of the work is the decoy calibration alone.

Why not just apply plain Benjamini–Hochberg to whatever p-values the detector implies? This only shifts the problem to where those p-values come from. Without a correctly specified null, Benjamini–Hochberg is either invalid or extremely conservative. Conformal Labeling reports 0.09% power for standard BH against 94.25% for its calibrated version on MATH-L5 (Selective Labeling with False Discovery Rate Control). Decoys supply the null.

Proposed Experiments

The primary testbed reproduces the single-cell asynchronous setup of Bian et al., 2023 and Bian et al., 2024: 400 potential devices within 1 km, 16 base-station antennas, Rayleigh fading with path loss, and a maximum delay spread of 4 symbol periods. We sweep the active-user count, the SNR, and the decoy ratio $m/N$ from 0.05 to 0.5. Metrics are realized FDR against target $\alpha \in \{0.01, 0.05, 0.1\}$, power (the fraction of active devices declared), the missed-detection rate at matched realized FDR, channel NMSE for declared devices, the confirmation rounds the deferral arm triggers, and runtime overhead.

The decisive check is a shift experiment. Thresholds and calibration pools for the baselines are tuned at one SNR and user load. Test frames are then drawn at different noise powers, path-loss spreads, delay spreads, and activity levels, including loads above the tuning point. The proposal succeeds if three things hold: decoy calibration keeps realized FDR at or below $\alpha$ in every cell while the frozen threshold and offline split conformal exceed it somewhere, its power stays within a few points of the per-condition oracle threshold, and free-probability AMP gives clearly more power than Group LASSO and damped AMP under identical decoy calibration.

Three further checks probe the boundaries. Repeating the experiment with zero delay spread tests whether the benefit is specific to broken synchronization. Repeating it with a deliberately asymmetric denoiser, using user-specific priors not applied to decoys, should break validity as the theory predicts. Finally, adding decoy columns to the synchronous mmWave matrix-factorization receiver of Yuan et al. tests whether the method extends beyond pilot-based detection, replacing that receiver's singular-value-gap heuristic for counting users.