cs.LGNov 11, 2026

Probabilistic State Space Enumeration in Neural Network Computation

Authors: Victor O. K. Li, Yang Han, Jacqueline C. K. Lam

Organizations: ElohaX Ltd. · The Hong Kong University of Science and Technology (Guangzhou), China · The Chinese University of Hong Kong, Hong Kong SAR, China · CASBS, Stanford University, United States

Abstract

Many methods for pruning neural networks rank weights or groups of weights by importance and retain a single subset. We study how channel groups contribute jointly to the output of multilayer perceptrons (MLPs) in Transformer language models. Inspired by network reliability analysis, probabilistic state space enumeration (PSSE) represents the dense MLP output as the expected importance-corrected masked output over 2G2^G joint states of GG channel groups. Summing the most probable states' probability-weighted outputs gives an approximation whose absolute error is bounded by the omitted probability mass times the maximum masked-output norm. NORDER-II adapts ORDER-II to enumerate states in decreasing probability without sorting the full space. Its first BB states maximize the probability mass captured at that budget. A weight-entropy scorer fixes each layer's ordering from pretrained weights. We evaluate all 168 MLP layers across six models from the Llama, Gemma, and Qwen families on two datasets with 8, 16, and 32 channel groups. In all 1,008 comparisons, the 95%-mass prefix yields lower mean relative error than uniform sampling at the same state count, with or without bias correction. At all three group counts, it also yields lower median and 99th-percentile relative error than a single top-kk mask. For downstream inference, we use the number of distinct channels in each prefix to set pruned MLP widths. With one validation-selected group count per model, PSSE achieves lower perplexity than both top-kk pruning baselines in all 36 matched-FLOP settings. Our pruned decoder MLPs achieve mean speedups of 1.11×1.11\times, 1.23×1.23\times, and 1.36×1.36\times over dense MLPs at 10%, 20%, and 30% target MLP projection FLOP savings, respectively. PSSE offers a principled path toward both probability-mass-controlled approximation and more efficient inference in pretrained language models.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. How Should Reasoning Be Organized in a Transformer's Latent Space?

    Sep 12, 2026Hongyu Gu, Chang Liu, Jingwen FuTransformer AttentionImplicit Reasoning in Language Models

  2. Tracing Computation Density in LLMs

    May 26, 2026Corentin Kervadec, Iuliia Lysova, Iuri Macocco +2Transformer InterpretabilityLLM Interpretability