Top-$k$ decoding is a widely used method for sampling from LLMs: at each token, only the largest $k$ next-token-probabilities are kept, and the next token is sampled after re-normalizing them to sum to unity. Top-$k$ and other sampling methods are motivated by the intuition that true next-token distributions are sparse, and the noisy LLM probabilities need to be truncated. However, to our knowledge, a precise theoretical motivation for the use of top-$k$ decoding is missing. In this work, we develop a theoretical framework that both explains and generalizes top-$k$ decoding. We view decoding at a fixed token as the recovery of a sparse probability distribution. We introduce *Bregman decoders* obtained by minimizing a separable Bregman divergence (for both the *primal* and *dual* cases) with a sparsity-inducing $\ell_0$-regularization; in particular, these decoders are *adaptive* in the sense that the sparsity parameter $k$ is chosen depending on the underlying token distribution. Despite the combinatorial nature of the sparse Bregman objective, we show how to optimize it efficiently for a large class of divergences. We prove that (i) the optimal decoding strategies are greedy, and further that (ii) the objective is discretely convex in $k$, such that the optimal $k$ can be identified in logarithmic time. We note that standard top-$k$ decoding arises as a special case for the KL divergence, and construct new decoding strategies with substantially different behaviors (e.g., non-linearly up-weighting larger probabilities after re-normalization).

Xinmeng Huang, Shuo Li, Mengxin Yu, Matteo Sesia, Hamed Hassani, Insup Lee, Osbert Bastani, Edgar Dobriban. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

We study statistical estimation and inference for the ranking problems based on pairwise comparisons with additional covariate information. In specific, in this paper, we study a Covariate-Assisted Ranking Estimation (CARE) model in a systematic way, that extends the well-known Bradley-Terry-Luce (BTL) model by incorporating the covariate information. We impose natural identifiability conditions, derive the statistical rates for the MLE under a sparse comparison graph, and obtain its asymptotic distribution. Moreover, we validate our theoretical results through large-scale numerical studies.

Silicon photodetectors, such as photodiode (PD), are extensively used in optical sensing as their proper performance and low cost to achieve screen brightness adjustment, ambient light flicker detection, and other functions. With the rise of under-screen optical sensing, PD is no longer sufficient for low-light level light detection and real-time low light level flicker detection. While an emerging detector, single photon avalanche diode (SPAD), shows its advantage to ultralow light sensing. However, SPAD tends to saturate at high light levels, which limits its widespread application. To inspire ambient light sensor design and address these issues, this paper proposes a high sample per second (SPS), wide dynamic range (DR) and ultralow illuminance detection SPAD array system on chip (SoC). A$16\times 16$SPAD array architecture along with counter and charge-pump is designed in 180nm BCD process to sense 100μdux ambient light at 660nm. On-chip FFT processor of 2048 points with 32-bit accuracy is realized to process sampled optical waveform for flicker detection. Besides, an area-efficient integrated charge pump is implemented to regulate high-voltage (19~25V) to SPADs with on-chip digital auto-gain control (AGC), which improves the optical DR from 87db to 123db. This work extends the optical sensing range significantly and demonstrates the effectiveness of the proposed SoC with systematical measurements.

In recent years, full-duplex communications in a single frequency channel have become a practical technology. However, existing full-duplex medium access control (MAC) protocols can hardly take full advantages of full-duplex transmission opportunities, because they are not capable of adding one more half-duplex link on an on-going half-duplex link to form a full-duplex link. Besides, the exposed node and hidden node issues in multi-hop wireless networks limit flexible establishment of full-duplex links. Such limitations waste full-duplex transmission opportunities, and thus degrade network performance. In this paper, an efficient full-duplex link establishment protocol called full-duplex opportunity exploitation (FDOE) is developed to exploit full-duplex transmission opportunities in a wireless mesh network. FDOE leverages rateless coding and pseudo-noise (PN) sequences to establish a full-duplex link whenever a full-duplex transmission opportunity is available. Such a distinct feature leads to significant improvement of network performance. FDOE is evaluated through theoretical analysis and extensive simulations. Performance results show that FDOE exploits full-duplex transmission opportunities efficiently in wireless mesh networks, and thus significantly outperforms existing MAC protocols.

Integrated access and backhaul (IAB) networking is envisioned as a key technology to support more flexible and dense deployment of base stations (BSs). However, existing directed acyclic graph (DAG) based IAB networking highly limits the flexibility and efficiency of link scheduling, due to the fixed parent-to-child relation between two adjacent IAB nodes. In this paper, a mesh-architecture based approach is developed to improve the efficiency of IAB networking. The key idea of the mesh architecture is to make the relationship between two adjacent IAB nodes configurable. Based on the mesh architecture, the two-stage scheduling scheme of IAB networks is revised. The typical scenarios where the mesh-architecture based IAB networking outperforms the DAG-based one are analyzed. Simulation results show that the mesh-architecture based IAB networking can effectively improve the throughput by 6.70%40.56% and substantially reduce the delay under various traffic loads, as compared to the DAG-based IAB networking.