Systems that decide how much compute a language model should spend on each question usually rely on a small learned predictor that reads the model's hidden state and guesses how likely the model is to solve the question. That guess is a single number. When it is wrong, and it is most often wrong on unfamiliar question types, the allocator acts on it with full confidence. It pours samples into hopeless problems or starves solvable ones. We propose to give the difficulty predictor a posterior over its own weights, cheaply, with a Laplace approximation (a Gaussian fitted around the trained weights using local curvature). The predictor's output then becomes a distribution over each question's solve rate rather than a point. That distribution serves as a prior in a sequential sample-allocation rule, and the prior is updated after every verified sample.
In two sentences: the allocator should trust the predictor where the predictor is confident and fall back to learning from observed samples where it is not. Parameter uncertainty is exactly the quantity that tells it which case it is in. This matters most under distribution shift, which is the regime where current adaptive-compute methods are reported to break.
Core Claim
Consider an input-adaptive allocator that decides how many samples to draw per query under a fixed batch budget. It performs better, and degrades more gracefully under distribution shift, when two things hold. First, its per-query success estimate is a posterior derived from weight uncertainty in the predictor. Second, that posterior is combined with outcomes observed during sampling.
The mechanism is Jensen's inequality applied to the "at least one success in $k$ tries" objective. Let $p$ be a query's per-sample success probability. A point estimate $\hat p$ predicts failure after $k$ samples with probability $(1-\hat p)^k$. A posterior predicts $\mathbb{E}[(1-p)^k]$, and for $k \ge 2$ this is never smaller than $(1-\hat p)^k$ when $\hat p$ is the posterior mean, because $(1-p)^k$ is convex in $p$. The point-estimate allocator therefore misjudges marginal value in a predictable direction. It believes an uncertain query is "done" too early. It also keeps paying a constant $\hat p$ per sample on queries it wrongly rates as marginally solvable, and it has no principled way to revise that belief after repeated failures.
Relation to Prior Work
The motivating evidence comes from the adaptive-compute side. Learning How Hard to Think trains a two-layer MLP on base-model hidden states to predict marginal reward per sample and allocates Best-of-$k$ budgets from it. The file reports that noisy, over-optimistic point predictions caused over-allocation to impossible queries, which forced an ad-hoc offline binning step. Thought calibration uses linear probes with conformal calibration to stop reasoning early, and it finds that supervised point probes lose calibration out of distribution. We treat both as evidence that the predictor's own ignorance is the missing variable. The LLM Already Knows and Optimizing Reasoning Efficiency through Prompt Difficulty Prediction confirm that hidden states carry difficulty signal, which justifies building on hidden-state predictors rather than replacing them.
The method comes from the point-estimation side. Bayesian Low-rank Adaptation for Large Language Models fits a post-hoc Kronecker-factored Laplace approximation over LoRA weights. It reports Expected Calibration Error dropping from about 31.2% to about 2.1% on Winogrande-small at unchanged accuracy, and it finds that uncertainty lives substantially in lower layers, so a last-layer approximation is insufficient. We reuse this technique on a difficulty head rather than on a task model.
The closest intersectional works each keep one piece fixed.
- Bayesian reward models for LLM alignment applies Laplace-LoRA to a reward model to penalize uncertain candidates in Best-of-$N$. The sample count $N$ stays static; we instead use uncertainty to set the count.
- Adaptive Rollout Allocation for Online RL, known as VIP, fits a Gaussian process over prompt embeddings to allocate training rollouts toward prompts near $p\approx 0.5$. We allocate at inference, target a different objective (at least one verified success rather than gradient variance), and place uncertainty on a learned hidden-state predictor rather than a kernel model.
- Zero-Overhead Introspection (ZIP-RC) predicts a joint distribution over reward and remaining length. That distribution is aleatoric and learned by distillation, so it cannot express that the introspector itself is off-distribution.
- ODAR routes with fixed thresholds and uses token varentropy. Varentropy mixes genuine multi-path ambiguity with model ignorance, which is the conflation that A Survey of Stochastic Simulation and Optimization Methods in Signal Processing and On Sampling from the Gibbs Distribution with Random MAP Perturbations warn against when a mode is mistaken for mass.
- Adaptive Generate-Rank-Verify (ADAP) doubles search budgets geometrically, and does so blind to content. It is the natural uncertainty-free, content-free competitor.
Mechanism
A difficulty head $f_\theta$ reads the base model's prompt hidden state and outputs a logit for $p(x)$. The head is trained on labeled solve rates, following Damani et al.'s data regime of roughly 3,000 verified queries. A Kronecker-factored Laplace posterior over $\theta$, with LoRA on the head and on the last few base layers, gives a predictive mean $m(x)$ and variance $v(x)$ for $p(x)$ via linearized prediction. We moment-match these to a Beta$(a_x, b_x)$ prior.
After drawing $k$ samples with $s$ verified successes, the posterior is Beta$(a_x+s,\, b_x+k-s)$. Under the posterior Beta$(a,b)$, the probability that the next $j$ samples all fail has the closed form
$$ \mathbb{E}\big[(1-p)^j\big] = \frac{B(a,\, b+j)}{B(a,\, b)}, $$
where $B$ is the Beta function.
The allocator runs in rounds. In each round it gives the next sample to the unsolved query with the largest one-step gain in success probability, $1 - \mathbb{E}[(1-p)]$ under that query's current posterior. It stops a query at its first verified success. The same closed form supports lookahead over $j>1$ if myopic greedy proves too short-sighted.
A confident "impossible" prior (small $a$, large $b$) gets essentially nothing. A wide prior gets a few probing samples, and repeated failures then push its mass toward zero automatically. This replaces Damani et al.'s offline binning with Bayesian updating.
Research Program
The work has three parts. First, we build the Bayesian difficulty head and check its calibration in and out of distribution. Second, we implement the sequential Beta allocator and a batch version that fixes the total budget across a query set. Third, we measure allocation quality against an oracle.
The oracle is built by drawing a large number of samples per query offline to estimate true $p(x)$, then computing the optimal allocation for each budget. This lets us report regret, meaning the gap to oracle success at matched budget, rather than raw accuracy alone.
The primary domain is code with executable tests, because success is observable at test time. We train on TACO and evaluate both in distribution on TACO and under shift on LiveCodeBench, the benchmark on which ADAP was reported. The secondary domain is math. There we train on Numina-COT and shift to AIME 2024 and HMMT. The observed success signal is a reward-model score thresholded into pass or fail. This is noisier, and we report it separately rather than pooling.
A third, adversarial shift uses the inverse-scaling-ttc tasks from Inverse Scaling in Test-Time Compute. On those tasks more compute can lower accuracy, and we check that an uncertain prior plus observed failures stops spending rather than chasing distractors. All methods share one open base model at the 7B scale, one sampler, and one verifier.
Baselines
The naive reference is uniform Best-of-$k$, with the same $k$ for every query at each total budget. The strongest a-priori method is Damani et al.'s MLP marginal-reward allocator with offline binning, reimplemented on the same hidden states, training set, and budgets. The file reports that it matches standard Best-of-$k$ success on Math and Code with half the samples (50% compute reduction, Learning How Hard to Think). Beating it means reaching the same success rate with fewer total samples in distribution, and a clearly smaller regret under the TACO-to-LiveCodeBench shift.
The strongest content-blind competitor is ADAP. The file reports ADAP as 5.5× cheaper on coding and 2.9× cheaper on math than the best fixed-budget policy for reaching 100% success on solvable problems (Adaptive Generate-Rank-Verify). We run it with the same verifier and cost accounting.
We also run Early-stopping Self-Consistency-style sequential stopping with a flat Beta(1,1) prior, which is our allocator with the predictor removed. For alternative uncertainty sources we run a five-member deep ensemble of difficulty heads and a Gaussian process over hidden states in the style of VIP, each converted to a Beta prior the same way. Every predictor gets the same labeled data and the same hyperparameter search budget, selected on an in-distribution validation split only.
Two ablations isolate the key ingredient. The plug-in ablation keeps the Laplace-trained head but feeds only its mean $m(x)$ to the allocator, using a very concentrated Beta. This tests whether the variance, not the training, drives any gain. The constant-spread ablation gives every query a Beta with the same global variance, tuned on validation. This tests whether per-query uncertainty matters or whether any prior spread suffices. A last-layer Laplace variant tests Yang et al.'s finding that lower-layer uncertainty matters.
Why not just…?
Why not just use an ensemble of difficulty heads instead of a Laplace posterior? An ensemble is a legitimate way to get the same kind of epistemic signal, and it is in the experiments on equal footing. Our claim concerns feeding the predictor's uncertainty into a Bayesian allocation rule, not the Laplace approximation specifically. If ensembles match Laplace, the contribution stands and the recommendation becomes "use whichever is cheaper." Laplace's advantage is that it is post-hoc and needs one training run.
Why not just temperature-scale or conformally calibrate the point predictor? Calibration fixes average miscalibration on the calibration distribution. Thought calibration reports that its guarantees weaken exactly when exchangeability fails out of distribution. A temperature-scaled point estimate also still has no per-query spread, so it cannot trigger the Jensen correction or learn from failures. We include a temperature-scaled Damani baseline. If it closes the OOD gap, that is strong evidence against our thesis, and we will report it as such.
Why not just skip the predictor and learn difficulty online from the first few samples? This is the most serious threat. The flat-prior sequential baseline and ADAP both embody it, and on large budgets they may match us, since observed outcomes eventually dominate any prior. The predictor should pay off at small budgets, where a few probing samples are a large fraction of spend on easy and impossible queries alike. The Bayesian version should also never be worse than the flat prior, because a wide prior reduces to it. We will report the budget at which the curves meet. If that budget is very small, the honest conclusion is that a-priori difficulty prediction adds little.
Why not just use VIP's Gaussian process? A Gaussian process over hidden states is another Bayesian predictor and is run as a baseline. The open question is whether a fixed kernel on high-dimensional hidden states gives useful uncertainty relative to a Laplace posterior over a learned head. VIP only showed its value for training-time rollout allocation, not for inference budgets.
Decisive Checks
The central experiment plots success rate against total samples, with oracle regret, for every method in three conditions: in distribution (TACO), under shift (LiveCodeBench, AIME/HMMT), and on inverse-scaling tasks. Each is paired with Expected Calibration Error of the predicted $p(x)$.
The pattern that supports the claim has three parts. In distribution, the Bayesian allocator matches the Damani baseline. Under shift, it matches or beats the flat-prior online allocator. Only it avoids the failure mode of each regime.
Two ablations serve as the sharpest tests. The first requires that the plug-in-mean ablation lose most of the OOD gain. The second requires that per-query variance correlate with predictor error on shifted data, with the top uncertainty decile holding a disproportionate share of large $|m(x)-p(x)|$ errors. If the constant-spread ablation performs as well as the full method, per-query parameter uncertainty is not doing the work, and we will say so.
References
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- Thought calibration: Efficient and confident test-time scaling
- The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations
- Optimizing Reasoning Efficiency through Prompt Difficulty Prediction
- Bayesian Low-rank Adaptation for Large Language Models
- Bayesian reward models for LLM alignment
- Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
- Zero-Overhead Introspection for Adaptive Test-Time Compute
- ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference
- A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
- On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations
- Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
- Inverse Scaling in Test-Time Compute
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning