acceptodds
Under review as a conference paper at ICLR 2027

Probabilistic State Space Enumeration in Neural Network Computation

Abstract

Deep neural networks typically realize dense computation by propagating information through all intermediate channels, while many approximation methods rank and retain individual computational components. We ask whether dense neural computation can instead be represented exactly as an expectation over a combinatorial state space, and approximated by evaluating only its most probable configurations. We introduce a novel probabilistic state-space framework for Transformer MLPs. The framework partitions the intermediate dimension into channel groups, defines an input-dependent distribution over binary inclusion states, and uses importance-corrected masked outputs such that the full expectation exactly recovers the dense MLP output. The key algorithmic novelty is NORDER-II, which enumerates complete joint states in decreasing probability without constructing or sorting the exponentially large state space. Truncating this ordering yields an anytime approximation governed by cumulative probability mass and a state budget. On Llama-3.2-1B and Gemma-2-2B, NORDER-II at a state budget of B=2048 achieves 92.4% and 93.8% MLP-output approximation accuracy, compared with 76.9% and 79.8% for Channel Top-k. When the first, middle, and last MLP layers are approximated jointly, WikiText-2 perplexity remains within 0.06% and 0.54% of dense inference. Relative to expected-count Grouped Top-k, NORDER-II yields 82.6–126.4% relative accuracy gains with only 0.18–0.19% additional local analytic FLOPs. These results establish the significance of joint-state structure beyond atomic salience and point to a new paradigm for neural computation: dense layers can be viewed as structured probabilistic inference over combinatorial computational states. This framework opens a path toward adaptive, probability-mass-controlled computation in pretrained neural networks.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
probability-ordered traversal, joint neural states, combinatorial state spaces, transformer MLPs, language models, neural computation, subset enumeration, sparsification, efficient inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_zaNUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents a masking approach for the feed-forward passes in a transformer model attention block's fully connected layers, based on choosing high-probability configurations in the exponentially large state space of masking configurations. The paper presents the NORDER-II method, which constructs a probability distribution over the state space and then chooses the highest probability states, without enumerating the exponentially large state space. Authors experiment on three blocks of the Llama 3.2-1B and Gemma models, reaching comparable or improved predictive performance over several baseline masking methods, and comparable performance to the baseline un-masked model. The method is also shown to be empirically equivalent in computational costs w.r.t. the baseline masking methods.

Critical strengths

The idea presented is very interesting and could lead to efficiency gains in terms of computations in terms of throughput FLOPS in transformers. Such gains could be highly valuable, given that much of the computational costs over the lifetime of a transformer lie in the inference computations. The usage of an algorithm that can find the highest-probability states in a exponentially large state space and the usage of a joint state space, and then applying this to masking is also a very interesting and, to my knowledge, novel idea that is worth exploring further.

Critical weaknesses
  • The paper is not sufficiently clear and rigorous in defining the method presented. Key aspects are left unclear on how the method works, justifications for choices made are not given, and where the novelty of the work lies. A key idea in the paper is this ability to sort an exponentially large state space by state probabilities, which is highly interesting but not well explained. The paper builds on the ORDER-II method but does not define it in the main text, nor the key operations used. At least the general idea should be presented, and the reader referred to the original publication. This is necessary for the reader in order to distinguish what is the novel contribution that NORDER-II makes on top of ORDER-II. Furthermore, many definitions and equations contain notation that is not defined, and key choices are not properly justified. For example, a key aspect of the method is having a sensible masking probability distribution, but the choices for the masking probability distribution used in the paper are not well justified or explained. Another example is how the masking groups are formed, and therefore what is being masked in the MLPs. These factors make the results difficult to reproduce without substantial guesswork, and difficult to evaluate the contribution.
  • The overall motivation is left unclear in the main text and experimental results. The abstract states that the method opens a framework for probability-mass controlled computation, but it is left unclear what are the actual benefits of this are. My guess is that it is reduction in FLOPS, but I did not see any experiments comparing FLOPS of the masked approach compared to the original model. Furthermore, it appears to me that the construction of the mask itself requires evaluating the full network and then masking outputs (masked output F(x,z)F(x,z) requires construction of mask zgz_g for layer c(x)c(x), but construction of zgz_g requires the un-masked output of c(x)c(x)), eliminating any computational gains to be had as far as I can see.
Questions for authors
  1. What is the motivation for choosing this form for the masking probability distribution construction outlined in the paper (Eq. 5-6)?
  2. Is the NORDER-II (or ORDER-II) algorithm optimal in finding the correct ordering of the highest probability states by decreasing probability?
  3. Are efficiency gains in terms of FLOPS the main motivation for the method? If so, what are the efficiency gains in FLOPS that NORDER-II provides over the baseline model? How many groups are activated on average for the states chosen?
  4. How is the weight group partitioning done in practice for the Llama and Gemma model experiments? There are several approaches I can imagine. For example for G=12, 1) Each intermediate MLP layer (gate_proj, down_proj, up_proj) in every block independently partitioned into 12 groups 2) Combined weights of a single block's MLP are divided into 12 groups 3) Is the set of weights in all three blocks combined divided into 12 groups?
  5. Could you provide the mathematical definitions for μn(x),σn(x)\mu_n(x), \sigma_n(x), as well as an explanation of what nn refers to (Eq. 6)?
  6. Why are only 3 blocks experimented with, and not the whole model?
  7. Were experiments repeated for multiple random seeds, and if so, what are the means and standard deviations for the results?
  8. Did the authors empirically test how much wall-clock time does the method require compared to the baseline model?
Reviewer_rUUBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Research paper represents Transformer MLP output model as expectation over binary masks that include or exclude groups of intermediate channels with importance correction (so that full expectation equals output). Proposed NORDER-II algorithm lists these masks in order of decreasing probability and finally provides approximation of MLP output. Numerical experiments on Llama-3.2-1B and Gemma-2-2B provide comparison with random masks, channel top-k, grouped top-k.

Critical strengths
  1. Exact and simple decription. Importance-based masks give exact expectation of dense output and worked examples allow for easier checking.

  2. Clear algorithm. Enumeration procedure is described clearly with cost analysis and evaluation on two recent language models.

Critical weaknesses
  1. No computational benefit. Group probabilities are computed from norm of each group contribution. Final output is weighted sum of all group contributions. Proposed method first computes every group contribution, which already gives exact dense output. Approximation can only be worse than result that is already available. Research paper itself states that comparison is devoted to present the speed improvements.

  2. Theory part is simple. Theorem 3.1 follows from linearity of expectation. Theorem 3.2 follows from triangle inequality. Enumeration algorithm is based on known method from reliability analysis.

  3. Comparison is not matched. Channel top-k and grouped top-k keep only part of channels or groups. NORDER-II keeps weighted sum over all groups. Higher accuracy is expected and does not show value of joint states.

  4. Limited evaluation and strong claims. Two small models, three layers and WikiText-2 sample are used. With 16 groups probability target is not reached within computing budget, scaling is unclear. Claims about new paradigm for neural computation are not supported by presented results.

Questions for authors
  1. How proposed method can reduce computation if group contributions must be computed before probabilities and final output?

  2. What is advantage of NORDER-II compared to exact dense output that is available once all group contributions are computed?

Reviewer_RETiOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors of this paper ask whether dense neural computation can be represented as an expectation over a combinatorial state space, and approximated by evaluating only its most probably configurations. Their key algorithmic novelty is NORDER-II, which enumerates complete joint states in decreasing probability without needing to materialize the entire state space. Preempting this ordering then yields an anytime approximation government by cumulative probability mass and a state budget.

Critical strengths
  • I think the authors make a technically valuable contribution: they can efficiently enumerate the most probable states, and the truncated expectation is an unbiased approximation of the true value.
Critical weaknesses
  • The biggest weakness in my opinion is that I do not think the authors have presented sufficient evidence that evaluating transformer MLPs is a bottleneck, and perhaps more importantly, that this is a particularly useful approach for sparsifying, and therefore accelerating, such computation. To put it bluntly, my concern is that the paper demonstrates how to approximate something that is already cheap to compute exactly, with an approximation that is not actually cheaper.

  • Another weakness is that the method is limited by the number of groups it can handle: for G>12, it appears to suffer from the curse of dimensionality where one would need to enumerate an excessive number of states to reach the desired probability threshold.

Questions for authors
  • Is there a reason why the partitioning only happens during the down projection, i.e. equation 3, and not in equation 2?

  • More of a recommendation than a question: the importance reweighting in lines 151-161 appear seemingly out of nowhere. I would recommend gently walking the reader through why we need it to begin with, because otherwise our stochastic representation becomes biased, or at the very least alluding to that fact.

  • Could you please say more about your choice of group probability construction?

  • Could you please explain the significance behind the estimator admitting a "coefficient collapsed" computational form? I'm not sure I follow lines 209-222.

  • The random baselines that is compared against exhibits a peculiar behavior: it has a very high cosine similarity, but the scale appears to be completely off (almost in proportions to the retained probability mass). Is there any explanation for that? Could we construct another baseline that does not suffer from such weird scaling

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.