A Simple Model of Inference Scaling Laws
Authors: Noam Itzhak Levi
Venue: ICML 2025 poster (2025)
Keywords: Scaling Laws
Inference Scaling
Maths
Coding
LLMs.
Primary area: deep_learning->theory
TL;DR: We provide a simple predictive model for the functional behavior of inference with increasing number of attempts.

Abstract: Neural scaling laws have garnered significant interest due to their ability to predict model performance as a function of increasing parameters, data, and compute. In this work, we propose a simple statistical ansatz based on memorization to study scaling laws in the context of inference. Specifically, how performance improves with multiple inference attempts. We explore the coverage, or pass@k metric, which measures the chance of success over repeated attempts and provide a motivation for the observed functional form of the inference scaling behavior of the coverage in large language models (LLMs) on reasoning tasks. 
We then define an "inference loss", which exhibits a power law decay as the number of trials increases, and connect this result with prompting costs. We further test the universality of our construction by conducting experiments on a simple generative model, and find that our predictions are in agreement with the empirical coverage curves in a controlled setting. Our simple framework sets the ground for incorporating inference scaling with other known scaling laws.

A Simple Model of Inference Scaling Laws
Noam Levi
Abstract
While the scaling laws literature focuses on test perform- ance induced by pre-training, scaling during inference-the process by which trained model makes predictions on new data-has received less attention.
Neural scaling laws have garnered significant in- terest due to their ability to predict model per- formance as a function of increasing parameters, data, and compute. In this work, we propose a simple statistical ansatz based on memorization to study scaling laws in the context of inference. Specifically, how performance improves with mul- tiple inference attempts. We explore the coverage, or pass@1 @k metric, which measures the chance of success over repeated attempts and provide mo- tivation for the observed functional form of the inference scaling behavior of the coverage in large language models (LLMs) reasoning tasks. We then define an "inference loss", which exhibits a power law decay as the number of trials increases, and connect this result with prompting costs. We further test the universality our construction by conducting experiments on a simple gener- ative model, and find that predictions are in agreement with the empirical coverage curves in a controlled setting. Our simple framework sets the ground for incorporating inference scaling with other known scaling laws.
Recent works have shown empirically that LLMs can gain substantial benefits from repeated prompts to perform better on difficult tasks such as coding and formal proofs, where verification of the correct answer can be done (Brown et al., 2024; Snell et al., 2024; Bansal et al., 2024). These works demonstrate that the performance of weaker models can be amplified without further training by repeating inference trials, giving rise natural question:
Can we interpret, or predict the inference scaling behavior model with repeated altempts?
To answer this question, we propose a simple toy model that isolates the inference scaling laws which dictate how certain performance metries improve as a function of the number of inference attempts.
Inspired by the work of Hutter (2021), which introduced model to study scaling behavior for memorization and generalization capabilities, we devise simple setting to capture the effect of repeated inference attempts, focusing on the coverage metric, also known as pass@k.
In this work, we present analytical predictions for cover- age from probabilistic perspective and demonstrate how inference improves with the number of repeated trials in predictable way, which matches the observed behavior in (Brown et al., 2024) and (Snell et al., 2024).
1. Introduction
Advancements in deep learning have demonstrated that the performance of neural networks scales predictably function of model size, dataset size, and computational re- sources (Hestness et al., 2017; Kaplan et al., 2020a; Rosen- feld et al., 2020; Henighan et al., 2020a). These trends, known colloquially as neural scaling laws, have motivated research into understanding how scaling influences model performance in wide range of domains, but in particu- lar Large Language Models (LLMs) (Brown et al., 2020; Hoffmann et al., 2022).
We use two different approaches to obtain the predicted pass@k, @k, and highlight the connection between coverage and total inference cost. Additionally, we define a simple "inference loss", similar to the familiar test loss, but allow- ing for repeated trials, and predict its scaling.
Our main predictions are verified by empirical results on mathematical reasoning tasks for several LLMs, follow- ing Brown et al. (2024).
'école Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland. Correspondence to: Noam Levi <noam.levi@epfl.ch
Lastly, we test the universality of our theory on an entirely different generative model. We train Variational Autoen- coder (VAE) (Kingma and Welling, 2022) to generate re- constructions of its training data by sampling from a latent
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Simple Model of Inference Scaling Laws
space with an associated temperature. We find that the same behavior persists for both LLMs and the VAE setup, in spite of the vast differences in models and tasks.
(Yao et al., 2023) introduced ToT reasoning, which scales the CoT approach by structuring reasoning paths trees, allowing for exploration of multiple reasoning paths sim- ultaneously. These methods draw inspiration from earlier works like AlphaGo (Silver et al., 2016) and AlphaZero (Silver et al., 2017), which demonstrated the effectiveness of self-play and guided self-trajectory training in complex decision decision-making making tasks. Additionally, the concept of self- consistency, as discussed by (Wang al., 2022), employs majority voting over multiple reasoning paths to improve answer accuracy. These collective efforts aim to enhance the reasoning abilities of LLMs by refining their inference processes and scaling their reasoning capabilities, poten- tially leading to scaling laws for performance (Wu et al., 2024). However, the way these inference processes scale with the number of inference attempts is poorly understood.
Given that our results are isolated from the effects of other neural scaling laws, they could be incorporated into a broader exploration to find the optimal train/inference point. In particular, we hope this work sets the ground for explor- ing the optimal trade-off between training and inference attempts, such that the total performance is improved while cost is minimized.
The rest of the paper is organized as follows: In Section 3, we discuss our main setup, analogizing large models to per- feet memorizers. We explain how this model can lead to the empirical pass@ curves for LLMs in Section 4, and provide an interpretation for the parameters of the model as defining an effective perceived difficulty for the dataset. We further connect these parameters with compute costs in Section 4.3. In Section 5, we reaffirm our results us- ing a controlled simple generative model. We conclude in Section 6 and discuss future directions.
3. Memorizing Ansatz
In the following, we first briefly review the simplest model which produces the known data scaling law prediction by appealing to memorizing construction, then consider our proposed model for repeated inference attempts.
2. Related Work
The Hutter model (Hutter, 2021) is probabilistic frame- work originally introduced to study the scaling behavior of learning curves, focusing on the relationship between memorization and generalization. It assumes a model which perfectly memorizes features during training, allowing it to correctly match sets of features and labels {í, y such that only unseen features can incur an error. The set of features is assumed to follow a Zipf power law decay with parameter a, where the probability of encountering feature is 0, x i i-1-a and decreases with its rank. For training samples, the expected single feature error F, is
Neural Scaling Laws: Scaling laws for neural networks have been extensively studied in recent years. Empirical research has shown that error rates decrease predictably as a function of increased data, parameters, and compute, follow- ing power-law relationships Notable contributions in this space include work by Kaplan et al. (2020b). who demon- strated consistent scaling behavior across language models, and Henighan et al. (2020b), who extended these ideas to multimodal models, as well as Cabannes et al. (2024); Maloney ct al. (2022); Bordelon et al. (2020); Spigler et al. (2020); Caponnetto and De Vito (2007); Steinwart et al. (2009); Fischer and Steinwart (2020); Cui et al. (2021); Levi and Oz (2023; 2024); Nam al. (2024) who studied scaling laws for solvable yet sufficiently complex models, ranging from generalized linear regression random fea- ture models to kernel ridge regression, connecting them to results from random matrix theory and the underlying properties of the data.
1
E, = E[E,] = Σ 0,(1 -.)--,))- 0.)a = 12 3 B = 1+a
(1)
Equation (1) captures the average likelihood of encountering and labeling the feature incorrectly after n training samples. Similar to this model, we will adopt the idea of memoriz- ation as a surrogate for training, but will depart from the finite training set assumption as a basis for test errors.
While most scaling laws focus on training, the study of inference scaling remains under-explored. Our work strives to fill this gap by studying how performance improves with repeated inference attempts.
3.1. Perfect Sample Memorization, Imperfect Predictions
Recent advancements in infer- ence scaling and reasoning within LLMs have been signi- ficantly influenced by techniques such as Chain-of-Thought (CoT) prompting and Tree-of-Thour CoT prompting, explored by (Wei al., 2022), enables models generate intermediate reasoning steps, enhan- cing their problem-solving capabilities. Building upon this,
Inference and reasoning:
In contrast to the Hutter model, we focus on a scenario where all samples up to the model capacity nee have been memorized, hence there is no notion of test error coming from unseen data. Instead, failure during inference or data generation could arise from the need to follow a sequence of steps to reach the correct answer.
(ToT) reasoning.
Concretely, we consider a joint model of memory M and in-
2

---

A Simple Model of Inference Scaling Laws
1.0
0 5.5 = 88 0.08
2.8hia.2.8BB MATH
Llama-3-8B MATH
Gemmai2B MATH
1000.0
(Oracle Verifier)
(Oraclo Verifier)
(Oraclé VerifBor)
0.8
Sample Distribution
p
--889x
07.of
0.95x
0.1
Passšk
0.6
Pythia-2.8B MATH (Oracle VerifBer)
10-5
0.4
Laama-3888 MATH
(Omcle Verifier)
10-9
0.2
PDF
Gemma-2B MATH
CDF
(Oracle Verifier)
10-13
0.0
10 100
1000
104
0.0
0.2
0.4
0.6
0.8
1.0
k
Failure Probability p
Figure Pass@k and failure distribution curves for various LLMs on difficult tasks, against theoretical scaling predictions. Left: The relationship between pass@k and the number of samples for several coding and maths tasks for different models, as described (Brown et al., 2024), compared with analytical predictions presented in Equations (7) and (13). solid curves are data, while the dashed curves are the predictions from Equation (7), where and | correspond to the concentration of easy and hard problems. respectively. The dotted curves are the results Equation (13). The functional form in both cases captures well the LLM pass curves for various models, by adjusting o, p. Right: The Beta(o,, (8) distributions for the failure probabilities shown for the different models. We can see that most of the questions are "difficult", while the left tail behavior informs us regarding the rate of improvement with additional trials the "easier" samples. For example, the right panel demonstrates that Pythia- perceives the MATH dataset having a larger density of difficult questions (PDF concentrated at pa close to 1), while Llama3-8B finds the same dataset easier.
ference I. The memory is M E == X + y, where the samples are identical to the labels { = {y: 1 and corresponds to model which simply learns to memorize its training data. The inference model E H N- > M takes an input index which serves as a proxy for a particular prompt or task, and should produce the associated memor- ized label (sample) y4 by recalling it from the memory M. The inference model is taken to be imperfect in its retrieval, and subject to some error e, it makes predictions
to be correct.
The rest of our analysis relies on the following assumptions:
Assumption 3.1. For every sample i, we have access to a perfect verification method, which can determine if there exists correct generated answer during inference [(i) Vt- among k possible candidates (T)( ............. (1))
Assumption 3.2. Inference attempts (T) ... (t)) are independent and identically distributed (i.i.d)) random vari- ables.
T(i)- { Us +
with probability Ps+ Vis with probability 1 -i,
We note that Assumption 3.1 sets aside the important topic of the quality of answer verification. In tasks such as coding and formal proofs, automatic verification is often possible, as candidate solution can be quickly identified to be correct by proof checkers (Zheng et al., 2021). Likewise, unit tests can be used to verify the correctness of candidate solutions to coding tasks (Jimenez et al., 2024). How the following analysis changes we relax this assumption to the case of an imperfect verification method is an interesting question that we postpone to future studies.
for any sample 1. I....,, Re- For samples outside the model capacity the prediction always wrong [(1) yt-
At this point, we only accept perfect model "answers", such that the performance of the model on a single sample is measured simply by
A(i) (v.) (T(i))
(3)
where 1y(x)= if x y' else is the indicator function.
We start from the general case, where each sample has unknown failure probability p; [0, 1] at inference, and we are interested in the probability of at least one successful generation of a sample over k attempts. This is in-line with the type of reasoning tasks studied by (Snell et al., 2024; Brown et al., 2024), where the performance of a model requires only one correct answer, rather than every answer
Under Assumption 3.2, the probability of the model failing all k trials for sample within its capacity with failure probability p; is simply
P(k failures on sample i)
I[ A.()) =p. (4)
3

---

A Simple Model of Inference Scaling Laws
where l is the trial index. Therefore, the probability of at least success in & trials averaged over the entire dataset of size n, known as pass@k k, is given by
240 a 0.3,af
A5, aut us8 tike 03 a99 Goage MBLe 0
0.50
p 0.9 07
pass@k
The x
Σ
Re
Ila
&
A((0)
(5)
Luuercacce
Pythia-288B
0 of 28
MATI (Oracle
t=1
Verifier)
Re
Llama-3-S8
= -Ax
0.10
MATH (Oracle
The
Gemma-28
MATH (Oracle Verifier)
0.05
where we define the fraction of samples the model can store as ne/n E [0, 1]. describing the maximal potential pass@k k for a given model. This will the metric we use describe inference accuracy for the rest of this work.
10
100 1000
104
Figure 2. Inference attempts loss Linterence (k) for repeated at-
4. Power Law Distributions Predict Inference Scaling for LLMs
tempts on mathematics tasks. The inference loss as function trials for the LLM experiments in (Brown et al., 2024).
The setup described in Section 3 is completely specified by the distribution of failure probabilities p;- To construct the failure distribution, assume that different samples may have different inference complexity levels, incorporating some "easy" and some "difficult" samples with respect to the inference model.
averaging over the p distribution.
To test these predictions, we utilize the reported pass @ results of (Brown et al., 2024), which evaluated Gemma- 2B (Team et al., 2024), Llama3-8B (AI@ Meta, 2024) and Pythia-2.88 (Biderman et al., 2023) on mathematical and coding tasks. Here, we take the results for the MATH data- set, which consists of difficult math word problems (Chen et al., 2024), where 128 random problems from the test set were chosen for evaluation.
One way to model the different complexities is to appeal the so-called Beta distribution. We think of the failure probability across samples itself p p; random vari- able, drawn from p Beta(a, 9), whose probability density function (PDF) is given explicitly by
In Figure 1, we show that the functional form of pass @k given in Equation (7) is a good approximation for the empir- ical pass@k curves for the LLMs evaluated on mathematical tasks, as reported in Brown et al. (2024).
Beta(a, B:p) p 11 (1-p)-143 -149
(6)
B(a,3)
At large values, find power-law decay of the effective average failure probability
where B(a, (3) is the Euler beta function.
The Beta(ax, B3 distribution parameters are a E R+ which controls the amount of "easier" problems in the sample dataset, where smaller a pushes the distribution mass wards zero, while 3 R+ dictates how often encounter "harder" problems. Namely, a lower 3 parameter increases the distribution mass towards the right tail (high failure probabilities).
A (1-
T(3)K-B)
pass @
= R=+00
B(a,
(8)
which is a common feature in neural scaling laws (Bahri et al., 2024). we then define the inference loss Linterence (k) as the expectation with respect to the sample distribution over errors, our results for pass @k correspond
We can therefore compute the pass@k metric by simply averaging over the failure distributions as
Linference (k) = EE (Error in l trials) = T(A x x²)
(9)
I(3) +a)
R A
1
B(a, B)T(K aa 3)
pass
pass@k- @k = Ax
1
R AX (1-
1(3)--8
n1
A A B(a,
//'
dpp kP 1ta (1 - (1-p)-1p))))) -1+
= Ax
1
Bla,8 3)
This result implies that the model test loss with repeated inference steps will decrease mainly depending on the value of the exponent 3. Intuitively, it means that for a fixed parameter, the harder the questions appear to the model, the more inference attempts are required to reach low loss. We illustrate this behavior Figure 3.
I(3) +a)
Ax 1
B(a, ()T + t
where [(2) is the Euler gamma function, and indicates

---

A Simple Model of Inference Scaling Laws
mffrrnnce
L Inferemee
106
20
10s
0.8
10
0.7
15
0.6
1000
0.5
10
100
0.3
10
0.2
0.1
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
B
Figure 3. Inference attempts loss Linterence (k) for repeated attempts on the memorizing model for different parameter choices. Inference loss for different B and & values. Different colors indicate inference loss values at fixed (left) and at fixed k = 10 (right), illustrating behavior of Equation (9).
4.1. Interpretability
the trials space k;
The result in Equation (9) not only allows one to predict a threshold for inference in order to get an increase in model performance on difficult problems, but could also offer some interpretation for the difficulty of tasks with respect to the trained model.
f(k) = (p 1o00 doe doe a0 (1---9)-1tz
(10)
B(a,
- -fo0 doe doe f(o).
This interpretation implies that is possible to derive the probability distribution function of the samples terms of their perceived difficulty by performing the inverse transform. In particular, given an empirical pass@k met- ric obtained for given model, the inverse transform f(k) = (A pass @ will yield the perceived diffi- culty PDF Potentially, such procedure can be used to identify "difficult" and "easy" questions and construct im- proved fine-tuning algorithms by choosing training samples biased towards the "difficult" but obtainable tasks.
We can gain some insights regarding the real-world models by fitting the pass@k metric according to Equation (7) to the ones given in (Brown et al., 2024), and attempt to in- terpret the properties of the test data from the parameters and B. In particular, note that the ratio a a+-ğ gives the mean of the Beta distribution, which represents the average failure probability across the samples. If a 3, the mean failure probability is high (i.e., most samples are harder). On the other hand, if a < 8, the mean failure probability is low, implying that most samples are easy. Furthermore, the denominator a + B governs the concentration of the distribution, where large a + means that the failure probabilities Pt are more tightly clustered around the mean (more homogeneity in difficulty).
4.2. Correlated Trials and Effective & Approach
In the previous section, we showed that correlated samples drawn i.i.d. from varying complexity distribution can ef- fectively describe the pass@k metric for memorizing mod- els. Here, we take converse approach, where do not sume that samples are correlated through their failure rate distribution, but instead that trials themselves are correlated.
From Figure 1, we can see that the typical values for the "harder" problem parameter / ~ 0.35, while the tail para- meter is < a < 20. This implies that most of the problems the datasets used measure the pass curves were in- deed difficult terms of the model's perception, while the existence of left tail implies that the easy samples are covered quickly with less than 100 trials. This is reflected in the right panel of Figure 1.
One can conjecture that dependencies between trials arise due to the internal model structure and the data itself. To capture these correlations, we suggest model where the correlation between trials decays power law, imply- ing that successive trials become less independent increase the number of trials.
An additional point of interest would be connecting the ob- served empirical pass @k curves with the unknown failure probability distribution of the different models. This can be done by noting that the average (p*), performed Equa- tion (7), can be thought of performing a Laplace trans- form from the failure probability variable log (1/p) to
@ass@k
In order to incorporate the correlation between trials, we define the notion of an effective number of independent trials, denoted keft. This adjusts the original k to account for the decay in trial independence. The correlation between trials is modeled via power-law decay in the eigenvalues
5

---

A Simple Model of Inference Scaling Laws
passgik
1.0
N2 5x
P
10
F= 10
10
10
0.9
0.90
0.8
M, N, N,
10
0.50
10
possok
0.7
F"110
0.00
0.6
10
10
0.5
0.80
0.4
Ll8ma-388 MATIF
1000
0.30
1000
0.3
10
(Omalee Verifier)
10
10'5
10
10'7
10
10'5
10
10
10
10
10
10
C
C
Figure @ass@k as function of total inference cost Llama-3-8B MATH (Oracle Verifier). Left and Center: We show the pass @ metric function of number of total inference cost and number of FLOPS per token F number of prompt/decode tokens N, = Na in log, log. We see that there is clear trade-off between total inference cost whenever keeping one of the parameters fixed, a predictable way from Equation (16). Right: We show slice of the contour plots for fixed N₂ Na. and changing the number of FLOPS per token. The parameters chosen for these figures are fitted from Equation (7) applied to the data taken from (Brown et al., 2024).
of the correlation matrix, such that the effective number of independent trials is given by
4.3. Connection to Compute Scaling
Here, we would like to translate our results from the attempts variable to the inference cost. A natural proxy for the in- ference cost may be the number of required Floating Point Operations Per Second (FLOPS) For concreteness, we adapt the total inference cost formula suggested in (Brown et al., 2024), given by
Rief Σ ドー= (K),,,
R20,
(11)
where & is the power-law exponent governing how quickly the correlation between trials decays, (x)n) is the Har- monic number, and ((s) the Riemann function. At the large inference trial limit, Equation (11) asymptotes to
C = N X
(14)
where C is the total inference cost, Np. Na are the number of prompt and decode tokens, respectively, and F is the number of FLOPS per token.
( K 1-
k k
Kieff k0000
((K)
(12)
Thus, the probability of least one success in & trials, incorporating correlations, becomes
We can convert some of our pass@1 k results to this metric by taking the large limit of Equation (7), giving
pass@k Ax
1 11-1
n
Kell pi
Ax (1111111l (x)))))
k = (14 (-passsk) B(a, 3) ))
(A
AL
-1/3
(15)
(13) hence the resulting coverage is simply
R A x p(à - - +(())))(())))
Coverage(C)) R A. (1 I(3)
C (C-Np)
(16)
B(a,
Na
where p = pt is the error probability of every sample, and ken accounts for correlations between trials. The result of Equation (13) is shown in Figure as the dotted curves, which approximate the LLM behavior well for >>>>> We stress that this approach should be taken an effective de- scription, which nevertheless manages to accurately capture the same behavior as sample correlations.
where C = C/FFss the normalized total inference cost. Keep- ing all uncontrollable parameters fixed, such as the number of FLOPS per token fixed, we see from Figure that is worthwhile to reduce the number of prompting and de- coding tokens or increase the number of attempts, up to
'This may be crude of system efficiency (Dehghani et al.. 2021), which may benefit from repeated sampling (Juravsky et al., 2024; Zheng et al., 2023), as pointed out in (Brown et al., 2024).
metric that ignores other aspects
6

---

A Simple Model of Inference Scaling Laws
Temgerature
Original Images
Input
Encoder
Latent
Decoder
Output
Reconstructed Images
Space
Figure Visualization of the task described in Section Hcre, a VAE is tasked with generating samples from training data, where "failure" occurs when the reconstruction falls above certain threshold
Empirical vs Theoretical Pass@k with Correlation
Reconstruction Error Distribution for Multiple Trials
10
10a
Reconstruction Error
Pass@k
Empirical Passgi
Theoretical Fast@k (Threshold, c-0.1)
Empirical Pass@k
Theoretical Pass@k (Threshold,
Empirical Passglk
10-1
Theoretical Fassgi (Thresholld c-0.5)
10a
10a
10a
10a
102
k (Number of Trials)
Image Rank (sorted)
Figure 6. Results for the VAE reconstruction task, compared with semi-analytical predictions. Left: The pass@k k metric as a function of number of attempts for different threshold values, with temperature T = 1.1. The curves have been normalized to asymptote for visual clarity. Right: The reconstruction error behavior across multiple trials, indicated by different colors. The errors obey quasi power law behavior.
the minimal amount of total inference compute required to reach a target coverage. The numbers Figure 4 are chosen to mimic the results found in (Brown al., 2024), and are only meant give an illustration of the functional behavior of Equation (16).
to accurately reconstruct "memorized" examples, heuristic- ally shown in Figure 5.
this, we train a VAE with a temperature parameter to study how errors propagate over multiple trials and com- pare empirical pass@ @ k with theoretical predictions under correlated trials. We refer to this the VAE reconstruction task.
Alternatively, can phrase Equation (16) in terms of the inference loss as
Linference (C) Ax I(3) B(a,3) 3) N₂
C
No
-8
To quantify the error probability of the model over multiple samples, we define the error per sample using the norm of the difference between the reconstructed and original image:
(17)
which demonstrates the power law decay of the inference loss with total inference cost, depending on the value of
11 yill 33
error (1)
(18)
5. Experiments on a Simple Generative Model
Here, Y/ represents the original image, and ÿ is the recon- struction. This per-sample error metric allows us to define success or failure at the sample level, where trial is con- sidered successful the reconstruction error falls below threshold
To further validate some of our analytical understanding in a controllable setting, we perform series of experiments in which we train simple generative model to reconstruct images taken from FaSSion-MNIST (Xiao al., 2017). Our goal is to connect the theoretical memorizing model and the behavior of more complex generative models by attempting
To empirically calculate pass@k, sample multiple recon- structions from the VAE for each input sample. For each

---

A Simple Model of Inference Scaling Laws
Reconstruction Error Trial Correlation Eigenvalues
To complete the picture, empirically confirm that the assumption of independent trials is indeed violated, as trials are effectively correlated. To capture this effect, we compute the correlation matrix for the errors across trials Ckk
Empinical
10a
Reconstruction Error
10
n Σ e x crror;
Ekk''
(19)
10
10-1
The eigenvalues of the correlation matrix decay as a power law, suggesting that the effective number of independent trials diminishes as & increases, which clearly depicted in Figure 7 (left).
10
10
10a
10a
6. Conclusions
Trial Rank (sorted)
In this paper, we have proposed simple statistical explana- tion for a so-called inference scaling law, which describes the scaling the coverage (pass (aass@)) metric with number of repeated attempts for generative models. We presented two possible models which lead to inference scaling: One based introducing a sample space distribution of "easy" and "difficult" problems, and the other on an effective Zipf-like correlation structure between trials. Using these simple con- structions, we were able to derive analytical predictions for the pass@ k, as well the test loss as function of repeated attempts, which we dubbed the inference loss. We then verified our predictions empirically both through previous experimental results for LLMs and for a simple generative VAE construction.
Correlation Matrix of Errors Between Trials
0.106
200
0.104
0.102
0.100
0.098
800
0.096
We stress that the merit of our construction is in its sim- plicity, and there are many other models who can give rise to the same functional behavior. We view this as a posit- ive rather than a negative, since it means that this simple model captures universal behavior, which should not de- pend much on the modeling itself. For instance, another way to arrive at a similar scaling law would be to choose different modeling for the failure distribution, based per- haps on program length, and introducing the notion of a distribution of program lengths corresponding to different samples, similar to Ringel and de Bem (2018). . In the end, this type of construction will have similar interpretation in terms of task complexity w.r.t the model.
200
400
600
800
Figure 7. Correlation matrix for errors across different trials for the VAE reconstruction task. Top: The eigenvalues of the correlation matrix follow power law decay with the number of trials. Bottom: Visualization of the correlation matrix itself shows clear correlations between different trials for & = 1000.
sample, conduct & trials and calculate whether at least one trial resulted in reconstruction with error less than some chosen threshold value E [0, 1]. Pass @k is then computed as the fraction of samples for which the model succeeded to reconstruct at least once in l trials.
We believe our toy model offers simple yet effective phe- nomenological framework for understanding how inference quality improves with more opportunities to predict cor- rectly. Future work could extend this framework to more complex models, including applying similar methodology (Maloney al., 2022) to generalized linear regression, kemnel regression and neural networks, and investigate how it interacts with existing scaling laws based on model size and training data.
In Figure 6, we show the pass@k results for the VAE re- construction task, for different threshold values (left), as well as the reconstruction error distribution for multiple at- tempts (right). The theoretical predictions for the pass @k curves are shown for the effective l approach, given in Equa- tion (13), and approximate the VAE results well. Here, is computed empirically by taking the distribution at the maximal & and x is taken from the correlation matrix in Fig- ure
8

---

A Simple Model of Inference Scaling Laws
Acknowledgements
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirho- seini. Large language monkeys: Scaling inference compute with repeated sampling, 2024. URL https: / wwaxxiv.org/as...... /407 21787.
We thank Yohai Bar-Sinai, Alon Beck, Itay Lavie, Nadav Outmezguine, Zohar Ringel and Antonio Sclocchi for fruit- ful discussions. The work of NL is supported by the EPFL Al4science program.
Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters, 2024. URL https: https////xxvvv.rrrbbbboe
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal con- sequences of our work, in particular due to the large model sizes considered in this work, but we do not feel there are specific aspects of this work with broader impacts beyond the considerations relevant to all large machine learning
03314.
Hritik Bansal, Arian Hosseini, Rishabh Agarwal, Vinh Q. Tran, and Mehran Kazemi. Smaller, weaker, yet better: Training IIm reasoners via compute-optimal sampling. 2024. URL https://api htt.ps://ap...mmmtiicchh...... org /Ctopp/aD::221144600
semanticscholar.
models.
Marcus Hutter. Learning curve theory, 2021. URL https:
References
/ //arxiv. www.iiioogg/aaaaa/aooaaaaaaaaaaa wttp.//oo///bb///..00007... 04074.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learn- ing scaling predictable, empirically. arXiv preprint arXiv: 11112004499 2017.
Diederik P Kingma and Max Welling. Auto-encoding vari- ational bayes, 2022. URL https://arxiv.or
abs/1312 6114.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020b. URL https:// arxiv. arxiv.org/abe wttp/rgg///bbooooe /ttp//201...88000
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scal- ing laws for neural language models. arXiv preprint arXiv:2001.08 08361, 2020a.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy, Benjamin Mann, Alec Radford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling, 2020b. URL https: //arxiv. org/ /////////// 2010 14701.
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the general- ization error across scales. In International Conference on Learning Representations. 2020.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010.14701, 2020a.
Vivien Cabannes, Elvis Dohmatob, and Alberto Bietti. Scaling laws for associative memories, 2024. URL https: http://axxvvv..///ae/
02984.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint wrXiv:200..1416 2020.
Alexander Maloney, Daniel A Roberts, and James Sully. solvable model of neural scaling laws. arXiv preprint arXiv:2210.16859, 2022.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034, PMLR, 2020.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. An empirical analysis of compute- optimal large language model training. In Advances in Neural Information Processing Systems, volume 35, pages 30016-30030, 2022.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymp- totic learning curves of kernel methods: empirical data versus
paradigm. Journal of Statistical Mechanics: Theory and Experiment, (12):124001, 2020.

---

A Simple Model of Inference Scaling Laws
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
529(7587)4844488, 28 January 2016. URL https:
/ /www. www.rattuee.... www.tuure.cooaaaaeoameeeeeeeea
David Silver, Thomas Hubert, Julian Schrittwieser, Ioan- nis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanc- tot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general re- inforcement learning algorithm. arXiv [cs.Al], 5 Decem- ber 2017. URL http:/ /twxiv.xvvvvv///aa//aaa//aaaa http://awwwwo..oaa////o/o/oo ab//2b 01815.
Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In COLT, pages 79-93, 2009.
Simon Fischer and Ingo Steinwart. Sobolev norm learn- ing rates for regularized least-squares algorithms. The Journal of Machine Learning Research, (1)):8464-8501, 2020.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang. Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv [es. CLJ, 21 March 2022. URL betp://arxiv.oro www.eiiii.org/aaaa.. /bs// 1217.1
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regres- sion: The crossover from the noiseless to noisy regime. In Advances in Neural Information Processing Systems, volume 34, pages 10131-10143, 2021.
Noam Levi and Yaron Oz. The universal statistical structure and scaling laws of chaos and turbulence, 2023. URL https: / arwii.aiiv..... wttg/bsgg////oooooeeo..//...esse 2211 01358.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical ana- lysis of compute-optimal inference for problem-solving with language models. arXiv [cs.Al], 1 August 2024. URL http: http/aaxxvvv/// org/ abss////////// 2408.4880 00724.
Noam Levi and Yaron Oz.
The underlying scaling laws and universal statistical structure of complex datasets, 2024.
URL https:: /tt///ixvvvv./// orgg/ abs/ 6.0.6.......... 14975.
Kunhao Zheng, Jesse Michael Han, and Stanislas Polu. Minif2f: a cross-system benchmark for formal olympiad- level mathematics. CoRR, abs/2109.000111111 001100 2021. URL https://arxiv.orgg/ /tw..b////.0011111
Yoonsoo Nam, Nayara Fonseca, Scok Hyeong Lee, Chris Mingard, and Ard A. Louis. An exactly solvable model for emergence and scaling laws the multitask sparse parity problem, 2024. URL https: /ttps///axxxvvoooo abs/2404. 17563.
Carlos E. Jimenez, John Yang, Alexander Wettig, et al. Swe- bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou Chain-of-thought prompting elicits reasoning in large language models. arXiv [cs.CL). pages 24824-24837, 27 January 2022. URL https:/pproceddnngs cc/paper__iile//peeeeeeeesssseep fties//papert22222/1eee @s550011554ec44111a007771ooolle pdf.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Si- fre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Pier Giuseppe Sessa, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélic ffrioi, Andrea Tacchetti, Anna Bulanova, Antonia Pater- son, Beth Tsai, Bobak Shahriari, Charline Le Lan, Chris- topher A. Choquette-Choo, Clément Crepy, Daniel Cer, Daphne Ippolito. David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, Muraru, Grigory Rozhdestwenskly, Henryk Michalewski, Ian Tenney, Ivan Grishchenko, Jacob Austin, James Keel- ing, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stan- way, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikula, Mateo Wirth, Michael Shar- man, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross Mcllroy, Ruibo Liu, Ryan
oc
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas I. Griffiths, Yuan Cao, and Karthik Narasim- han. Tree of thoughts: Deliberate problem solving with large language models. arXiv CLJ, 17 May 2023. URL
Christian
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Sch- rittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lil- licrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature,
10

---

A Simple Model of Inference Scaling Laws
Mullins, Samuel L Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Fein- berg. Wojciech Stokowiee, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Gi- ang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek An- dreev, and Kathleen Kenealy. Gemma: Open models based on gemini research and technology, 2024. URL ht tttpps: pttps://arksn /tw.ivivvvv.. org/
learning algorithms, 2017. URL https://arxiy:
org/absa /a///b////// wttp://18800000
Zohar Ringel and Rodrigo de Bem. Critical percolation as a framework analyze the training of deep networks, 2018. URL https: wtw.iviiiivv.////iv///aaa//aaaaa org/ /arg//b/////// 1800 02154.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6)1111112,, 2012.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017. URL https: // /arxiv. org/ abs 6980.
08295.
AI@ Meta. Meta llama 3. 2024. URL htw.:: //1amm. meta.com/1lamal
Stella Biderman, Hailey Schoelkopt, Quentin Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mo- hammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. Pythia: A suite for analyzing large language models across training and scal- ing, 2023. URL https:/::/// /ttp//axvvvvvvvv///vv//ee/a/aava org/ abs . 01373.
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: Process supervision without pro- cess, 2024. http: wwwp:/wwwwwww..///////o/oaooaa/ 24005. 03553.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121 (27), June 2024. ISSN 1091-6490. doi: 10.1073/ www.:ddd.oogg//..... 1073/pnas 2311878121.
pnas. 1878812, URL http: httt:::/dxxxd.....oooo
Mostafa Dehghani, Anurag Arnab, Lucas Beyer, Ashish Vaswani, and Yi Tay. The efficiency misnomer. CoRR, abs/2110.12894, 2021. URL https://arxiv..r abs/2110. 12894.
Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y. Fu, Christopher R'e, and Azalia Mirhoseini. Hy- dragen: High-throughput I1m inference with shared prefixes. ArXiv, 0abs/2402.05099 2024. URL https: //api, semanticscholar. org CorpusID: 267523163.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyra- kis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Efficiently programming large language models using sglang, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion- mnist: novel image dataset for benchmarking machine

---

A Simple Model of Inference Scaling Laws
A. Experimental Setup
Original
Original
Original
Original
Original
Original
Original
Original
Original
Reconstructed
Reconsiructed
Reconstructed
Reconstructed
Reconstructed
Reconstructed
Reconstructed
Reconstructed
Reconstructed
Reconstrucied 10
Figure 8. Examples of original and reconstructed samples from the VAE reconstruction task.
Here, we specify the experimental procedure used for the analysis in Section 5.
We utilize a Variational Autoencoder (VAE) with the following architectural details:
Input dimension: 28 x 28 784, corresponding to the flattened pixel values of the Fashion MNIST dataset.
Hidden dimension: 400.
Latent dimension: 20, controlling the bottleneck for information in the latent space.
Decoder:
The decoder reconstructs the original input through two fully connected layers, outputting 784-dimensional vector followed by sigmoid activation to ensure pixel values remain between 0 and 1.
Temperature parameter: A temperature parameter 1.1 is applied during the reparameterizztion step to control the variance of the latent variables, allowing us model uncertainty in the latent space more effectively.
The VAE was trained on the first 400 samples from the Fashion MNIST dataset. The loss function combines binary cross-entropy for reconstruction and the Kullback-Leibler divergence to regularize the latent variables. We ran the training for 1000 epochs using the Adam optimizer with learning rate x 10
To provide qualitative insights into the model's 's performance, we visualize several input samples from the Rashion-MNIST dataset along with their corresponding reconstructions in Figure 8. This allows to inspect both successful and failed reconstructions, and examine the types of errors the model makes.
B. Example of Memorizing and Inferring Model
This appendix details the experimental setup used to simulate a neural network as a "memory" system with cumple-specifie retrieval probabilities, and evaluation using pass@k k metric.
B.1. Dataset and Preprocessing
utilized subset of the MNIST dataset (Deng, 2012).
Subset Size: We selected the first N Nsamples 1000 images from the MNIST training set.
Unique Class Assignment: Each these Nsamples images was treated as belonging its own unique class. Thus, the classification task for the memory model involved Nammpies distinct classes. The label for the i-th sample in the subset was simply i.
Image Preprocessingg MNIST images, originally 28 x 28 pixels, were flattened into vectors of size Din = 784. Pixel values were normalized using the standard MNIST mean (0. 1307) and standard deviation (0.3081).
12

---

A Simple Model of Inference Scaling Laws
Memory Model: Training Loss
Memory Model: Training Accuracy
1.0
Training Loss
0.8
Accuracy
Loss
0.6
0.4
2
0.2
Training Accuracy
0.0
30
40
10
20
Epoch
Epoch
Figure 9, Training curves for the "memory" model in Appendix B.
B.2. Memory Model
The "memory" component was implemented as a simple Multi-Layer Perceptron (MLP).
Architecture: The MLP consisted of:
1. An input layer accepting D.x = 784 features.
2. A first hidden layer with 256 neurons, followed by ReLU activation function.
second hidden layer with 128 neurons, followed by a ReI.U activation function.
4. An output layer with N samples neurons (one for each unique class), producing logits.
Training Objective: The model was trained to perform classification, mapping each unique input sample to its assigned unique class index. The goal was for the model to effectively memorize its training data.
Training Parameters:
Loss Function: Cross-Entropy Loss (LCE).
Optimizer: Adam optimizer (Kingma and Ba, 2017).
Learning Rate: 1) 0.001.
Epochs: The model was trained for 50 epochs.
Batch Size: B 32.
Training loss and accuracy on the training set (which comprised all Namples unique items) were monitored per epoch. The expectation was for the model to achieve near wear-perfect accuracy, indicating successful memorization, as shown in Figure
Training Monitoring:
B.3. Probabilistic Retrieval Process with Sample-Specific Difficulty
To simulate a retrieval process where samples have inherent difficulties, we assigned a success probability to each sample. This approach differs from directly adding noise the model's output logits.
Sample Failure Probability Assignment: For each of the Noamples unique training samples s, an intrinsic probability of failing recall in single trial, Ps, was drawn from Beta distribution:
Ps Beta( 8s)
The parameters for this Beta distribution were set to ag = 0.3 and 8s = 0.5. This ensures that some samples are inherently "easier" (lower p.) or "harder" (higher p.) to retrieve. This Ps is fixed for sample s across all its retrieval trials, as shown in Figure 10.
13

---

A Simple Model of Inference Scaling Laws
Density
20
10
0
0.3
0.4
0.6
0.8
0.9
P(failure in one trial)
Figure 10.
Failure probability distribution for the inference model Appendix
Pass@k Curve
1.0
0.8
Pass@k Rate
0.6
0.0
100
1000
10000
k (Number of Independent Trials per Sample)
Figure 11. Pass @k curve for the inference model in Appendix B.
Simulating a Retrieval Trial: For a given sample a with its associated failure probability ps, single retrieval trial
was simulated as follows:
random number was drawn from uniform distribution, (4(0, 1).
2. If > Ps. the trial was considered "successful recall." In this event, it was assumed that the memory model would correctly identify the sample's true class as its top-1 prediction.
S Ps, the trial considered a "failed recall."
B.4. Evaluation Metric: @ass@k
The performance of the probabilistic retrieval process was evaluated using the Pass@k metric.
Definition:
For given sample s, Pass @k evaluates whether the true class of is successfully recalled (as defined above) in at least one of l independent retrieval trials.
Calculation:
14

---

A Simple Model of Inference Scaling Laws
For each sample in the dataset:
Up to Kmar- 10 independent retrieval trials were simulated.
If a successful recall occurred at trial / & k, the sample was marked as passing for all k' 2 (up to Kmar) for which pass @ks was being evaluated. The simulation for sample s could then stop. The overall Pass @k rate for given k the fraction the N Namples samples that passed trials.
The results are shown in Figure 11, with the precise phenomenology captured by the main text.
15


Reviews:
[{"review_id": "bq6ZcS2Kb5", "reviewer": "Reviewer_4E5M", "summary": "The paper proposes to study scaling laws for inference in a restricted setup where the model can potentially memorize the training dataset. The paper also shows that the theoretical predictions match empirical results on mathematical reasoning tasks for LLMs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 4E5M,  \nThank you for your positive reading of our manuscript. \n\nBelow, we address your comments/questions:\n\n**Weakness:**\n\n  *The caption for Figure 1 was quite dense* – In the revised version, we will shorten the caption, and move some of its content to the main text, namely L131 – 133 could be moved. Do you believe this will make the caption easier to understand?\n\n**Comments/Questions:**\n\n1)\t*The authors should include some motivational real-world examples where the memorization assumption holds (in approximation)* - As per your suggestion, we will include an appendix which contains a very simple neural network classifier which can memorize (approximately) its training data, combined with an inference model which is allowed to make mistakes based on the Beta distribution. This way we separate the memorizing assumption from the inference assumption.\n2)\tThank you for the correction, we will fix the mistake.\n\n**Questions:**\n\n1)\tRegarding the Beta distribution - The Beta distribution is a particular choice made in this paper, but it is certainly not unique, as we point out in the main text: *One way to model…*. The reason for this choice is the fact that the inference behavior differs for small $k$ and large $k$, and so at least a two-parameter distribution is required. For instance, using the classical Zipf law type distribution with a single decay parameter $\\alpha$ would only capture one of these limits. Other two parameter distributions would also be acceptable, but the interpretation will remain the same: the model perceives some inference tasks as “difficult” and others as “easier” depending on the two parameters of the distribution.\n\nWe hope that our replies are sufficient to raise the reviewer’s confidence in our work, and potentially accept the paper. We welcome any further questions and comments.", "claims_and_evidence": "The paper makes several assumptions about the setup (e.g. the model can memorize all the samples upto the model capacity (line 101 column2) or that the model makes an incorrect prediction with some probability or that Beta distribution can be used to model the distribution of difficulty of data points. Using these assumptions, the paper derives scaling laws and the theoretical results are shown to match the empirical results.", "methods_and_evaluation_criteria": "The paper largely focuses on theoretical results and while they could have used more complex dataset for their empirical results, it should be fine given the focus on theory.", "theoretical_claims": "I do have some questions about assumptions that the authors make (more of this in \"Questions For Authors\"). I could broadly follow the theoretical claims but I did not attempt to re-derive final expressions in different equations (e.g. equation 7, equation 9, equation 10). I should also say that I will rely quite heavily on the other reviewers to fully appreciate the theoretical contributions (as this is not my regular area of work) so the authors should focus on addressing their questions and concerns first.", "experimental_designs_or_analyses": "Given the focus on theoretical results, the experiments, while not exhaustive, seem sufficient to back up the main claims.", "relation_to_broader_scientific_literature": "I am not much familiar with this literature but the paper seems to build on previous works, in terms of scaling law analysis and the choice of the memorization setup. It also improves on the existing work by focusing more on the inference scaling laws and incorporating the number of inference steps in their analysis.", "essential_references_not_discussed": "I am not much familiar with this literature but the paper seems to cite relevant related work.", "other_strengths_and_weaknesses": "I found the paper (and some captions) to be a bit dense to understand. e.g. The caption for Figure 1 was quite dense. I found the experiments with Llama-3-8B to be well motivated and easy to follow.The paper makes both theoretical and empirical contributions and should be useful for the community", "other_comments_or_suggestions": "1. The authors should include some motivational real-world examples where the memorization assumption holds (in approximation)\n\n2. In line 425 (second column), \"Similar to ( Ringer..)\" should be \"Similar to Ringer.. \"", "questions_for_authors": "1. In section 4, why is beta distribution a good choice ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2drBYEuUfz", "reviewer": "Reviewer_kFgD", "summary": "This paper studies the paradigm of inference scaling and tries to identify the functional form that can help explain predict performance therein, i.e., building a scaling law with respect to inference budget (e.g., k in pass@k metric). The authors consider one of the simplest models for pretraining scaling laws from literature, proposed by Hutter (2021) (and originally dating back to several people in 1990s, including Amari), that considers a hypothesis class wherein the data has been perfectly memorized by the network. Assuming this perfect memorization, the rate of loss reduction can be shown to yield a power law under certain assumptions on the data distribution. The authors essentially extend this model to inference scaling, finding really good fits to the empirical results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer kFgD,  \nThank you for carefully reading our manuscript, we are glad that you found our theoretical analysis sound and our empirical results well backed. \n\nWe would like to address the various points you raised below.\n\n**Regarding Evidence**\n\nWe agree that the VAE results are interesting, and are happy to see that they were appreciated. To be honest, having discussed with other researchers and due to the broader interests of the community, we preferred to highlight the functional matching to the LLM performance rather than the more controlled VAE setting. If you believe this is sufficiently interesting to the community, we will try to highlight these results a bit more in the revised manuscript.\n\n **Regarding Broader Scientific Literature**\n\nAs far as we know, this is indeed the first theoretical model for inference scaling. From a brief reading of the Park et al. paper, we agree that there are interesting connections there, though their work is for in-context learning and ours was tested on inference without further context. It is not unreasonable to think that one way to interpret the in-context update to the representation as somewhat equivalent to resampling from the memory of the pre-trained model during inference. Perhaps in the ICLR setting our \"error probabilities\" are not fixed, but updated according to the context provided. We thank the reviewer for bringing this to our attention, and will add it to the related works. If the reviewer has more insights to share along these lines during the discussion period, possibly regarding something we've missed, we'd be happy to discuss it further.\n\n**Comments/Suggestions**\n\nThis is an extremely interesting question, and we agree that developing a mechanistic understanding of the memorization module ansatz would be a valuable complement to our simple model. Our goal in this work was to introduce a first model that provides a clear explanation of the key inference observation. Understanding how this final result emerges from training would be a natural extension.\n\nAs a next step—currently a work in progress—we aim to explore the connection between pre-training scaling performance and inference scaling in solvable models, which we believe exist. This direction may align with the reviewer's intuition, as memorization must occur during training, and we may observe different inference scaling behaviors depending on whether the \"memorization assumption\" holds or breaks down. Moreover, the simple model presented here seems to give quite universal results, but it still might be that there are several \"universality classes\", where different models might fall into. \n\nFinally, while we have not yet considered RNNs, their study should, in principle, be feasible, and would very likely lead to different scaling behaviors, at least in some cases (if not considering SSMs perhaps). \n\nWe appreciate this valuable suggestion and will certainly investigate it in future work.\n\nWe hope that our replies have affirmed your confidence in our work, and potentially lead to accepting the paper. We welcome any further questions and comments.", "claims_and_evidence": "The claims are well-backed with evidence: the empirics are thorough and consistency with theory is really nice. I really liked the VAE results---they were honestly the most exciting confirmation of the model and I'd have loved to see them emphasized more in the writeup.", "methods_and_evaluation_criteria": "Both approaches and results make sense, and I do not have any complaints.", "theoretical_claims": "Not quite applicable, since the model is an extension with fairly reasonable and well-motivated assumptions on the fitting parameters.", "experimental_designs_or_analyses": "Yes, see above.", "relation_to_broader_scientific_literature": "To my knowledge, this paper offered the first theoretical model for inference scaling. A very loosely related paper that comes to mind is by Park et al. (https://arxiv.org/abs/2501.00070), which in fact shows sample complexity of inference scaling for a belief update task (unlike the ones considered in this paper), is worse than a memorization based model would suggest, but nevertheless highly predictable. I'd actually be curious to hear authors' thoughts on that paper.", "essential_references_not_discussed": "Related work is fairly described in my opinion.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "Implementation: While the authors motivate their model of scaling with the memorization ansatz that derives from Hutter's work, it would have been better to see a more mechanistic argument for why we should expect such a model to transpire for a pretrained Transformer model. Is it possible the results are a consequence of specialized attention heads basically operating like perfect memorization modules? If not, then would we expect the scaling to be very different for a different architecture such that the proposed memorization model breaks down there? For ex., would inference scaling with an RNN not work. (I realize inference scaling with RNNs has not been shown, but I'm mostly asking for curiosity's sake here.)", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aj8A3ZzsXr", "reviewer": "Reviewer_FFcT", "summary": "The paper introduces a statistical framework to analyze the scaling laws for LLMs inference, particularly addressing how model performance (pass@k) improves with repeated inference attempts. The authors present 2 models, one assumes samples differ in difficulty, modeled via a Beta distribution; the other considers correlated inference attempts through a power-law correlation struction. Empirical validation is conducted on large language models (LLMs) and a Variational Autoencoder (VAE) trained on image reconstruction tasks, showing strong agreement between theoretical predictions and empirical data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer FFcT,  \n\nThank you for your positive appraisal of our submission. We’re glad that you found valuable insights and potential practical applications, which were our goals.\n\nWe address the weaknesses raised, as well as questions below.\n\n**Weaknesses**\n\n1)\t*strong assumptions* - We completely agree that both the independence assumption and the perfect verification limit are strong assumptions. However, given that our paper is the **first** to propose a model for inference scaling (as far as we know), it is natural to begin with a limiting, ideal setting and extend it in future works. It is rather surprising that even under these strong assumptions, the simple memorizing model captures the inference scaling behavior of real models as well as it does. \n\n   We would like to kindly bring to the reviewer’s attention the fact that the independence assumption itself is also discussed in the main text, and the “effectively correlated trials” section (Sec. 4.2) is meant to describe this effect, if we understand the reviewer correctly. We apologize if this point was not sufficiently clear, and will try to highlight it further in the revised version. \n   Furthermore, we are sure that relaxing the perfect verification assumption will be a very interesting avenue for future works, since verification methods is a very broad topic all in itself. \n\n2)\t*More diverse models* - We agree in principle that adding more diverse controlled experiments could extend the scope of the paper, but we believe that the current evidence on LLMs and VAE reconstruction supports our predictions. The VAE experiments are meant as intermediate step, that shares some of the complexity of LLMs without the full pipeline. If the reviewer has a particular experiment in mind that would make sense within the “memorization-inference” setup, which is neither VAE nor the LLMs, we would be happy to test our predictions on it.\n\n**Questions**\n\n1)\t*Scaling beyond tasks in the main text* - The experiments given in the main text which consider LLMs on reasoning tasks and the VAE reconstruction are different, but share some common features. In particular, in both tasks, the model is asked to “learn” the training data distribution and perform sampling (as opposed to regression for instance). In that sense, the exact details of the architecture, model and task are not particularly important, as long as the model can be thought of as a two component “memorization” module and  “inference” module. Therefore, our predictions are quite universal, as long as the data is not uniformly “easy”, and so we believe our results should extend to other generative settings, for instance to diffusion models.\n\n2)\t*Sensitivity to $\\alpha,\\beta$* - The question of sensitivity to the parameter choices is a bit unclear to us, since the conclusions (namely the inference scaling laws) are analytically given in terms of $\\alpha,\\beta$, so the exact dependence on the parameters can be characterized. Could the reviewer please clarify their meaning? If the question is of interpretation, then different choices of $\\alpha$ correspond to a different small $k$ behavior, since as we explain in the main text, the average “difficulty” of the samples is $\\frac{\\alpha}{\\alpha+\\beta}$, and so larger $\\alpha$ values would imply a slower improvement with $k$ for a smaller number  of trials, while $\\beta$ dictates the large $k$ behavior of the inference loss/pass@k, meaning how difficult it is to improve performance by increasing $k$ at a large number of inference attempts, where larger $\\beta$ means greater scaling improvement.\n\nWe hope that our replies are sufficient to raise the reviewer’s confidence in our work, and potentially accept the paper. We welcome any further questions and comments.", "claims_and_evidence": "The claims are supported by empirical experiments. The authors demonstrate that their proposed analytical framework for inference scaling match the empirical \"pass@k\" curves observed in multiple LLM experiments and VAE reconstructions. The findings indicate that inference performance improves predictably with repeated attempts.", "methods_and_evaluation_criteria": "The proposed methods are reasonable and suitable for capturing the inference scaling phenomena in LLMs and generative models. pass@k is a reasonable evaluation criteria for measuring model's performance in math reasoning and coding problems.", "theoretical_claims": "The paper provides analytical derivations for the inference scaling behavior under specific assumptions (e.g., independence and correlation of trials). The correctness of these derivations looks mathematically sound.", "experimental_designs_or_analyses": "Experimental designs for both the LLM-based mathematical tasks and the VAE reconstruction tasks are sound and appropriate.", "relation_to_broader_scientific_literature": "I am not sure about its relation to broader scientific literature.", "essential_references_not_discussed": "I am not sure about the essential references not discussed.", "other_strengths_and_weaknesses": "Strengths: The problem this work is trying to address is of practical significance. The findings offer valuable insights into practical strategies for balancing computational costs and model performance by adjusting inference attempts.\nWeakness:\n- The strong assumptions regarding independence and perfect verification limit the model's direct applicability in less controlled scenarios.\n- Using more diverse models (other than small VAE) could make the findings more persuasive.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could you clarify if your scaling law predictions hold when applied to tasks beyond mathematical reasoning or VAE reconstruction, especially for the tasks that cannot be verified easily.\nHow sensitive are your conclusions to the choice of parameters α and β in the Beta distribution? How will different choices of these parameters affect the estimation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W4USdmZIaX", "reviewer": "Reviewer_i2X4", "summary": "This paper investigates how neural models' inference performance scales with multiple attempts, particularly in the context of LLMs. The study introduces a straightforward statistical framework based on memorization to explore the relationship between inference attempts and success rates, measured by the coverage or pass@k metric. This metric reflects the probability of obtaining the correct answer across repeated attempts. The authors derive an \"inference loss\" that shows a predictable decay in error with increasing trials, linking it to prompting costs. They validate their model through empirical experiments with LLMs on reasoning tasks and a generative VAE model, confirming that their theoretical predictions align with observed data. The framework isolates the effects of inference scaling and proposes it as a foundational element for optimizing the trade-off between training and inference costs to enhance overall model performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer i2X4,  \n\nThank you for your careful and positive review of our paper, finding that our proposed model is simple and elegant. We hope that our responses will alleviate your concerns.\n\nBelow, we address the issues you raised.\n\n**Comments and Suggestions**\n\n1)\tThank you for pointing this out, we will complete L87: *For $n$ training samples, the expected single feature error $E_i$ is*.\n2)\tThank you for finding this typo, it will be fixed in the revised version.\n\n**Weaknesses  and Questions**\n\n1) *Data generation process* - While it is true that the data generation process of LLMs may seem very different from the simple memorizing model,  the claim of the paper is not that the simple model perfectly captures every detail of the LLM inference process, but rather the opposite – that these details are not crucial to address inference scaling, as it is often true with pre-training scaling laws [1,2]. \nThe only requirements from the LLM in order to fit our assumptions are that the model is sufficiently large, or has sufficient capacity to (approximately) store its training data, and that inference is done by an imperfect sampling process. The specific task we chose – which is recovering exactly the training data itself, is not what LLMs do, but it is a proxy for the task of “recovering the right answer from the training data”. Meaning that if the answer, or the path to the answer (a sequence of retrievals from its memory) existed in the training data, this model is able, with some error probability, to reach this answer. This approach explains why this simple model captures very different scenarios (LLM and VAE). In order to understand the precise connection between our model and LLM performance, it would be wise to study the internal representations of LLMs, and look for “memorizing modules”, possibly in specialized attention heads, as was suggested by reviewer kFgD, and will be part of the focus of our future works. We will better explain this point in the main text of the revised version, if the reviewer finds this answer acceptable and useful in understanding our goal.\n\n2)\t*Other functional fits to the data* - We agree with the reviewer that ablation with simple functions could be useful, we will include a short appendix considering several functions of the suggested type to show that they cannot be used to capture the full behavior of the model, typically sigmoid type functions are somewhat able to capture the small $k$ regime, but never both limits. We provide a preliminary  figure in https://imgur.com/kTsDM0R .\n\n3)\t*Similar parameters for different descriptions* - The parameters should not be the same, but there exists a simple mapping between them that can be derived from the large and small $k$ limits.\n\n4)\t*Beta fit to practical data* - Thank you for this comment. The two figures are conceptually different. Regarding Fig  4(c), we will include the empirical curves, which match very well the asymptotic behavior predicted by our model (https://imgur.com/a/8Ftb76R). Regarding Fig 1(b), this is a prediction made by our model that requires further study to properly interpret. In essence, this figure shows the \"difficulty\" distribution for the different models, on the specific set of maths questions. It does not fit any empirical data, but should be taken as the interpretation of the $\\alpha,\\beta$ parameters. The goal of the figure is to show that different models can perceive the same data at different difficulty levels, and a detailed study of this point could lead to new inference sampling techniques, based on the ratios of easy and difficult questions. We hope this explanation clarifies this point and would be happy to discuss further.\n\n5)\t*Figures 6(b) and 7(a) fitting the theoretical curve* - Figs 6(b) and 7(a) are meant to serve as qualitative evidence for the effective correlation between trials, rather than an exact characterization. A priori, the inference attempts themselves need not be correlated, but we see that there are effective long range correlations between different trials from both the reconstruction error 6(b) and its eigenvalues 7(a). We see that it is sufficient that only a bulk of the eigenvalues conform to a power-law decay to have good predictions for the pass@k metric. We will explain this point more clearly in the revised text.\n\n6)\t*emergent behavior at specific threshold value* -  The logic is that for larger threshold values the model must have smaller reconstruction error, and so require fewer inference attempts to succeed. The \"emergence\" is just a feature of the functional form of Eq. 7. It would be interesting to analyze this model in more detail and consider whether one can define \"emergence\" as the point where the function changes from concave to convex perhaps, and study the internal structure of the model at these points.\n\n**References:**\n\n[1]  Maloney et al. https://arxiv.org/abs/2210.16859\n\n[2] Bahri et al. https://www.pnas.org/doi/abs/10.1073/pnas.2311878121", "claims_and_evidence": "Some of the claims are not supported. Please refer to the questions for more details.", "methods_and_evaluation_criteria": "The proposed method and evaluation appear to make sense.", "theoretical_claims": "I ensure that the proof logic is correct.", "experimental_designs_or_analyses": "The existing experiments in this paper are sound, but some of the claims are not supported by the experiments. Please refer to the questions for more details.", "relation_to_broader_scientific_literature": "This problem is timely, as o1 and r1 are among the most popular research topics recently. The proposed model is simple and elegant. If the authors can address the concerns for this model, I believe it will inspire future reasoning models.", "essential_references_not_discussed": "I think all important references are included.", "other_strengths_and_weaknesses": "**Strengths**:\n\n1. The topic is timely and aligns with the current research trend in reasoning models. Pass@k is an important metric in these models, particularly for MCTS or exploration in RL. \n\n2. The proposed model is simple and elegant.\n\n3. It is encouraging to see that the proposed model performs well in the experiments, as evidenced by Figures 1(a), 2, 6(a), and 7(b).\n\n**Weaknesses**:\n\nI have several concerns about the proposed model:\n\n1. I have several questions regarding the practical aspects of data generation models. (Please refer to questions 1-4)\n\n2. Some of the experiments do not align well with the scaling laws. (Please refer to questions 5 and 6)", "other_comments_or_suggestions": "Some typos:\n\n1. In Eq. (1), $E_i$ is not defined;\n\n2. In line 305, \"asmyptotes\" should be \"asymptotes\".", "questions_for_authors": "1. This paper focuses on the inference scaling laws of LLMs. However, the data generation model appears to be not relevant to LLMs. I suggest that the authors discuss why the practical problems in LLMs that require inference scaling laws should follow the Hutter model.\n\n2. It would be interesting to investigate whether the proposed model is better than a simple power law scaling. An alternative model could be $pass@k = \\mathcal{A} \\times (\\text{Sigmoid}(\\alpha k) + \\beta)$. Can the proposed model fit the curve better than this simpler model?\n\n3. To fit Figure 1(a) with Equation (7) and Figure 2 with Equation (9), should we use the same set of parameters ($\\mathcal{A}, \\alpha, \\beta$) or different sets? According to the model, the same set of these numbers should be used given a model.\n\n4. In Figure 1(b), it is unclear how well the Beta distribution fits the practical data. The same issue arises for Figure 4(c).\n\n5. In Figures 6(b) and 7(a), only a small proportion of the data fits the theoretical curve well. Why does this happen?\n\n6. In Figure 6(a), the \"emergent behavior\" occurs when $\\epsilon=0.1$, but not for other values. Why is this the case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a simple theoretical model of inference-time scaling laws, with accompanying empirical validation. Overall, I agree with the reviewers' assessment: neither the experiments nor the theory are particularly groundbreaking on their own, but it is refreshing to see a simple, understandable theoretical model whose predictions are actually reflective of experimental practice. I recommend accepting this paper.
Decision: Accept (poster)