Picture many sensors, each allowed to send only one bit to a central decision-maker, trying to tell whether a weak signal is present. When the signal's shape is known exactly, the answer is settled. Each sensor computes the likelihood ratio, which measures how much more probable its data are with the signal than without, and sends "1" if that ratio exceeds a threshold. Theory says this deterministic rule is the best possible, and that adding private randomness only hurts. Most real alarms are composite, though: we know roughly what a signal looks like but not its exact direction, location, or type. For composite problems, a second body of theory proves the opposite. If all sensors share a common random seed (a "public coin"), distributed testing becomes dramatically cheaper. These two results have never been reconciled, and practitioners have no rule for choosing between them.
We propose a single family of one-bit rules that contains both extremes. Using the shared seed, every sensor draws the same random $k$-dimensional slice of the signal space. It computes the likelihood-ratio statistic for "signal present" restricted to that slice, then sends the one-bit thresholded result. At $k$ equal to the full dimension $d$, this is the deterministic local likelihood-ratio test and needs no shared randomness. At $k=1$, it is the random-projection scheme behind the public-coin results. The proposal claims that the best slice size $k^\star$ is set by three quantities: the number of sensors, the signal dimension, and the per-sensor signal-to-noise ratio. When the alternative has structure, such as sparsity or attack families, slices matched to that structure beat both endpoints. The project will characterize $k^\star$, build the detector, and test it on the synthetic and real benchmarks used in this literature.
Core Claim
The conflict in the literature comes from asking where the randomness lives. The quasiconcavity results of On Optimal Quantization Rules for Some Problems in Sequential Decentralized Detection and On optimal quantization rules for sequential decision problems show that, for a fixed pair of hypotheses, mixing quantizers privately lands at an interior point of a set whose minimum lies at an extreme point. That extreme point is a deterministic likelihood-ratio threshold. The public-coin gains in Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction and Optimal high-dimensional and nonparametric distributed testing under communication constraints come from something different. Shared randomness chooses which simple sub-problem the sensors jointly attack. Our rule keeps the bit itself deterministic given the slice, which agrees with the quasiconcavity results, and puts the randomness only in the choice of slice. This view predicts something checkable: public randomness should buy nothing when the alternative is simple, and its value should grow with how "directionless" the composite alternative is.
Concretely, sensor $i$ holds $n$ observations with sample mean $\bar X_i \in \mathbb{R}^d$. Its sensor group $g(i)$ shares a random $k$-dimensional subspace $S_g$ drawn from the common seed. With $P_{S}$ the projection onto $S$ and $\tau_k$ a threshold, the sensor sends
$$b_i = \mathbb{1}\{\, n\,\|P_{S_{g(i)}} \bar X_i\|^2 \ge \tau_k \,\},$$
which is the one-bit thresholded likelihood-ratio statistic for a Gaussian mean shift whose direction is unknown within $S_g$. The central decision-maker forms a statistic from group-level deviations, where $p_0$ is the probability that a bit equals 1 under no signal and $m_g$ is the group size:
$$T = \sum_g \frac{\big(\sum_{i\in g} b_i - m_g p_0\big)^2 - m_g p_0(1-p_0)}{m_g p_0 (1-p_0)}.$$
The threshold $\tau_k$ is chosen to maximize the Fisher information carried by one bit, following the per-sensor decoupling of Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios.
Positioning
This work builds most directly on three lines of research.
The first supplies the local building block. Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios showed that thresholding the local likelihood ratio, rather than the raw observation, cuts the number of sensors needed to match a centralized detector from about 3.3 times to about 1.53 times. It assumes one homogeneous detection problem and has no shared randomness. That detector is essentially our $k=d$ endpoint. Decentralized Data Reduction With Quantization Constraints justifies reducing to a likelihood ratio before quantizing when observations are conditionally independent. It also warns, through its "sufficiency paradox," that the reduction can be strictly suboptimal under dependence. We therefore restrict the main claims to conditionally independent sensors and treat dependence as a stress test.
The second line motivates the composite setting. The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints proves that threshold quantizers are optimal for simple binary tests. It also proves that interaction gains at most a factor of four there. Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints characterizes optimal channels as extreme points of a joint range set. Both papers stop at simple hypotheses and name composite testing as open. Recursive Distributed Detection for Composite Hypothesis Testing: Nonlinear Observation Models in Additive Gaussian Noise does handle composite alternatives, using a distributed generalized likelihood-ratio test, but it exchanges real numbers with unlimited precision. Our proposal sits in the empty cell between these: composite alternatives, one bit per sensor.
The third line supplies the public-coin rates we must match or explain. Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction separates public-coin identity testing at $\Theta(k)$ samples from private-coin testing at $\Theta(k^{3/2})$ under one bit per player. Optimal high-dimensional and nonparametric distributed testing under communication constraints reports a public-coin separation rate of $\rho^2 \asymp \frac{\sqrt d}{n}\sqrt{\frac{d}{mb}}$ when the total bit budget satisfies $mb<d$. Neither paper asks how these schemes compare to the deterministic local likelihood-ratio bit. Neither asks whether intermediate slice sizes do better.
Research Program
The analytical part has two pieces. The first is a heuristic power calculation for the Gaussian mean-shift model with $m$ sensors, $n$ samples each, and dimension $d$. For each $k$, it gives the signal strength $\rho^2$ at which $T$ reaches a fixed power. A rough calculation suggests why a crossover should exist. Under the $k=d$ rule, each bit shifts by an amount proportional to $n\rho^2/\sqrt d$, so detection needs roughly $\rho^2 \sim \sqrt d/(n\sqrt m)$. Under $k=1$ with shared directions, the signal is spread over $d$ directions but adds up coherently within a group, which favors $k=1$ when $m$ is large relative to $d$. We will make these regimes rigorous, check them against the rate in Optimal high-dimensional and nonparametric distributed testing under communication constraints, and identify $k^\star$.
The second piece is a reconciliation statement. When the alternative set shrinks to a single point, slicing cannot beat $k=d$, which recovers the threshold optimality of The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints. The gain from shared slices should then grow with an "effective dimension" of the alternative. We define this as the dimension of the smallest subspace family that covers the alternative set with constant probability.
The algorithmic part extends slice selection to structured alternatives. For sparse signals, slices are random coordinate subsets. For a finite family of attack templates, slices are spanned by subsets of templates. In both cases the shared seed fixes the slice, and $\tau_k$ comes from the Fisher-information criterion.
Baselines
The naive reference point thresholds the raw observation directly, $\mathrm{sign}(y-\tau)$, and fuses the bits by unweighted majority vote. Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios reports that raw thresholding needs about 3.3Q sensors to match a centralized detector with Q sensors. A Decentralized Bayesian Attack Detection Algorithm for Network Security shows that majority voting is suboptimal for heterogeneous data. Any slice size we recommend must clearly beat this baseline. Failing to do so would mean the evaluation is broken.
The strongest existing method is the deterministic local likelihood-ratio bit, which is the $k=d$ endpoint. On the sparse stochastic signal model we use the Im-1-bit LMPT of Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios, which reports needing about 1.53Q sensors to match a centralized detector with Q sensors (153 versus 100). We will reproduce that ratio before comparing anything. The proposal counts as beating this baseline if, on a composite alternative, some $k<d$ reaches the centralized detector's power with clearly fewer than 1.53Q sensors. It must also do no worse on the original single-alternative setting.
The second strong competitor is the fully directional public-coin scheme, which is the $k=1$ endpoint and our implementation of the random-projection design analyzed in Optimal high-dimensional and nonparametric distributed testing under communication constraints. That paper reports only analytical rates; no reported numerical result was found on Lacuna for it. We will therefore compare empirical separation curves against its rate formula rather than against a number.
All methods get the same data, the same number of sensors, exactly one bit per sensor per decision, and a fusion statistic calibrated to the same false-alarm level on held-out null data. Each method's free thresholds are tuned with the same particle-swarm budget used by Li et al.
Two ablations isolate the key ingredient. The first draws slices privately, one per sensor, so shared randomness is removed while slice size is kept. The second fixes deterministic coordinate blocks known in advance, which keeps coordination but removes randomness.
Why not just…?
Why not just use the deterministic local likelihood-ratio bit everywhere? This is the real threat. A simple calculation suggests it is hard to beat when the number of sensors is small relative to the dimension, and it needs no shared seed. Shared randomness should matter only once sensors are plentiful relative to the effective dimension of the alternative. If the experiments show that $k=d$ is never meaningfully beaten in any regime we test, the contribution shrinks to a reconciliation result. That result would show the public-coin advantage is vacuous for one-bit likelihood-ratio detection with many samples per sensor, which is still worth reporting. The sweep over sensor counts and dimensions is designed to decide this question.
Why not just let each sensor randomize privately? The quasiconcavity results of On Optimal Quantization Rules for Some Problems in Sequential Decentralized Detection say private mixing is strictly worse for a fixed hypothesis pair. The $\Theta(k^{3/2})$ versus $\Theta(k)$ separation in Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction says the same for composite testing. The private-slice ablation measures how much of any gain this accounts for.
Why not just assign fixed slices in advance instead of drawing them randomly? Sensors and the central decision-maker can agree on a fixed design, so in average-case settings "public coin" can amount to a pre-shared plan. For signals spread evenly over all directions, fixed coordinate blocks may perform as well as random ones. Against signals concentrated in a single block, however, only that block's sensors carry information, and random rotation spreads the signal across all groups. We will test both alternative types. We expect fixed blocks to suffice for spread-out signals and to fail on concentrated ones. If they suffice everywhere, we will recommend them.
Proposed Experiments
The first benchmark is the Gaussian white-noise mean-shift model of Optimal high-dimensional and nonparametric distributed testing under communication constraints. We sweep the dimension $d$ from 16 to 1024, the sensor count $m$ from $d/8$ to $8d$, the per-sensor sample size $n$, and the slice size $k$ over powers of two. Signal directions are drawn three ways: uniformly at random, sparse, and adversarially aligned with one block. The metric is the empirical separation $\rho^2$ at 90% power and 5% false alarm. The decisive check is whether the empirical $k^\star$ follows the predicted crossover in the ratio of sensors to dimension. If $k^\star$ sits at $d$ throughout, the core claim fails.
The second benchmark is the sparse stochastic signal model of Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios. We first reproduce the 1.53Q equivalent-sensor ratio and the threshold of about $1.482\sigma_w$. We then make the alternative composite by randomizing which subset of sensors carries the signal, and measure the equivalent-sensor ratio and ROC curves for each $k$. Under the original simple alternative, our method should match 1.53Q, not improve on it, which tests the reconciliation prediction directly.
The third benchmark is the KDD Cup 1999 data using the five continuous features of A Decentralized Bayesian Attack Detection Algorithm for Network Security. That paper reports a training minimum error probability of $9.3369\times10^{-4}$ and a test misdetection rate as low as 0.0013, both for Smurf attacks alone. We first reproduce the Smurf-only setting. We then make the problem composite: the null is normal traffic and the alternative is any attack family, with slices spanned by random subsets of attack templates estimated from the 10% training split. Because these features are dependent, this experiment also probes the sufficiency-paradox warning of Decentralized Data Reduction With Quantization Constraints. If $k=d$ outperforms all slices here while losing on independent synthetic data, that would localize the method's limits to dependence, and we will report it as such.
References
- On Optimal Quantization Rules for Some Problems in Sequential Decentralized Detection
- On optimal quantization rules for sequential decision problems
- Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
- Optimal high-dimensional and nonparametric distributed testing under communication constraints
- Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios
- Decentralized Data Reduction with Quantization Constraints
- The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
- Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints
- Recursive Distributed Detection for Composite Hypothesis Testing: Nonlinear Observation Models in Additive Gaussian Noise
- A Decentralized Bayesian Attack Detection Algorithm for Network Security