Convex-Hull Allocation of Reasoning Budgets

Language models that "think" before answering are usually given the same thinking budget for every question. That budget might be a fixed cap on reasoning tokens or a fixed number of sampled attempts. The cost of this uniformity is well documented. Easy questions waste tokens, and hard-but-solvable questions get cut off before the model reaches an answer. Video networking faced the same problem decades ago when sharing bandwidth across streams. Its answer was rate-distortion allocation: measure, for each stream, how much quality each extra bit buys, and give bits to the streams where they buy the most. The precise version of that rule has a step that current language-model allocators skip. Before comparing slopes, it keeps only the operating points that lie on the convex hull of each stream's cost-quality curve. Any stream whose curve has a dead zone followed by a jump is then either funded past the jump or not funded at all.

This proposal argues that the skipped step matters for reasoning models. Accuracy as a function of thinking length is often not concave. A hard problem may need several thousand tokens before any answer is correct, after which accuracy climbs steeply. Allocators that hand out compute one unit at a time by predicted marginal gain will see near-zero gain on the first units of such a problem and starve it. That is the "hard-but-solvable" class these methods were meant to rescue. We propose to predict a per-question curve over a two-dimensional grid of operating points: thinking-token budget crossed with number of samples. We take each curve's concave hull and allocate a shared budget across a batch with a single price per unit of compute. Questions whose hull never justifies that price are dropped deliberately.

Core Claim

Let $A_i(c)$ be the expected accuracy on question $i$ when it receives compute $c$, measured in generated tokens. The value $c$ can be reached by any combination of a thinking cap $B$ and a sample count $k$. Given a batch budget $C$, the allocation problem is to choose $c_i$ to maximize $\sum_i A_i(c_i)$ subject to $\sum_i c_i \le C$. The Lagrangian solution gives each question

$$c_i^*(\lambda) = \arg\max_{c \in \mathcal{P}_i} \; \big[A_i(c) - \lambda c\big],$$

where $\mathcal{P}_i$ is the finite set of operating points available for question $i$, including $c=0$ (skip), and $\lambda$ is a single price per token. The price is tuned by bisection until the budget binds.

Two consequences follow, and both are standard in video coding. First, the only points ever selected are vertices of the upper concave hull of $A_i$. Second, as $\lambda$ falls, a question jumps discontinuously from "skip" to "fund past the knee." Greedy marginal allocation agrees with this rule only when every $A_i$ is concave.

Our claim is empirical and falsifiable. On reasoning benchmarks, a meaningful fraction of questions have non-concave thinking-length curves. On those questions, hull allocation beats greedy marginal-reward allocation at equal total tokens. If the curves turn out to be concave, the two rules coincide. The contribution then shrinks to the joint token-by-sample grid, and we will report that outcome honestly.

Relation to Prior Work

The method comes from video networking. Delay-Constrained Video Transmission allocates bandwidth across video streams by equalizing each stream's rate-distortion slope against its deliverable rate per unit bandwidth. It uses a knapsack-style admission step that drops expensive streams, and reports 1.6x capacity over equal allocation and 2.2x to 3.5x more users than max-SNR scheduling. We borrow the slope-equalization rule and the admission step. We replace bandwidth with tokens and visual distortion with error rate. Work on cross-layer ranking of data units by reconstruction importance (On Cross-Layer Design for Streaming Video Delivery) motivates treating questions as unequal units rather than interchangeable ones.

Two papers already bring rate-distortion optimization to transformers, but neither touches test-time reasoning. Radio allocates weight bit-depths by stochastic dual ascent. Rate-Distortion Optimization for Transformer Inference compresses activations sent between an edge device and a server. In both, "rate" means bits, not reasoning tokens.

The closest work is Learning How Hard to Think. It trains a probe to predict the marginal reward of one more sample and allocates best-of-$k$ samples across a batch, matching static best-of-$k$ with half the samples. It also reports a result that bears directly on this proposal: fine-grained online allocation was fragile under prediction noise and underperformed coarse easy/medium/hard binning. We differ from it in three ways. We allocate over thinking length as well as samples. We optimize over the hull rather than greedily one unit at a time. We offer an explanation of the binning result: the hull restricts each question to a few vertices, which is a principled form of binning.

Several other methods also break uniform allocation but work along a single dimension or without a global price. ZIP-RC predicts a joint distribution of reward and remaining length from spare output logits and makes continue, prune, or branch decisions during generation. Latency and Token-Aware Test-Time Compute picks a search strategy per query by penalized utility. DIPA treats queries as bandit arms using training-free difficulty proxies, and explicitly lists joint thinking-token and sample allocation as open. OSCA mixes sampling configurations at the dataset level. DRQA fine-tunes a model to reason concisely. It is a change to the generator and is complementary to any allocator.

Research Program

The work proceeds in three stages.

Stage 1: measure true curve shapes. For a few thousand questions per benchmark, we run an open reasoning model across a grid of thinking caps from a few hundred to roughly sixteen thousand tokens. At each cap we force an answer and draw many samples. From these runs we estimate the per-sample success probability $p_i(B)$. With a perfect verifier, we compute best-of-$k$ accuracy as $1-(1-p_i(B))^k$. With majority voting, we estimate it by resampling. This gives an empirical $A_i$ over the full grid. We then report the fraction of questions whose curves are non-concave, and the share of achievable accuracy those questions hold. This stage alone answers whether the idea has room to matter.

Stage 2: predict curves cheaply. We train a lightweight head on the prompt's hidden state, in the style of The LLM Already Knows, to output the vector $p_i(B)$ over the budget grid. The sample dimension then follows analytically, so the head never has to learn it. We also test a training-free variant that fits the same vector from one short probe generation, using length and consensus signals as in DIPA. We will report the setup and labeling cost and compare them to the roughly 3,000 labeled queries needed by Learning How Hard to Think.

Stage 3: allocate under noise. Expected accuracy is linear in the predicted distribution, so the correct objective is the hull of the posterior mean curve, not the hull of a point estimate. We add shrinkage toward per-difficulty-tier mean curves. We then test the hypothesis that hull allocation with shrinkage keeps the robustness of offline binning while recovering the gains of continuous allocation.

Baselines

The naive reference point is uniform allocation: every question gets the same thinking cap and sample count, with that cap and count tuned on a held-out split to maximize accuracy at the matched total token budget. Every other method must beat this at equal tokens to justify itself.

The strongest competitor on this question is greedy marginal-reward allocation from Learning How Hard to Think. We extend it to the same token-by-sample grid so that the only difference is the allocation rule. It receives the same predictor, the same training labels and the same budget. We run both its online variant and its offline easy/medium/hard binning variant, because the paper found binning more robust. On its own setting, the file reports that this method used half the samples of best-of-$k$ for equal success, and gained up to 10% at fixed compute. We will reproduce its sample-only setting first, as a sanity check.

The strongest in-generation adaptive method is ZIP-RC. It reports up to 12% absolute accuracy over majority voting on AIME 2024 at the same or less average compute. We compare against it at matched average tokens on AIME 2024 and MATH-500.

The strongest training-free method is DIPA's bandit allocation, run with its recommended proxy per domain. For thinking length specifically, we include a uniform cap on top of DRQA-style concise reasoning. For DRQA itself, the file reports a 30.4% average token reduction with a 1.78% accuracy gain on Llama-8B.

Two ablations isolate the key ingredient:

  • Hull allocation versus greedy allocation, both run on oracle curves from Stage 1. This removes prediction error entirely and isolates the allocation rule.
  • Hull allocation with the skip option removed. This isolates the value of deliberate dropping.

Beating the baselines means a higher accuracy-versus-token curve than greedy marginal allocation and binning across the budget range. On non-concave questions, the gap should be statistically significant across three seeds. Overall, the method should at least match ZIP-RC at equal average tokens.

Why not just…?

Why not just use greedy marginal-reward allocation, which already works? This is the real threat. If thinking-length curves are concave, greedy allocation is already optimal, and hull allocation adds nothing on that dimension. The Stage 1 measurement and the oracle-curve ablation settle the question directly. Our prediction is that greedy allocation underfunds questions whose first few thousand tokens yield nothing. If the measured gap on oracle curves is negligible, we will drop the hull claim and present the result as a study of joint token-and-sample allocation.

Why not just stop sampling once answers agree, as early-stopping self-consistency or DIPA's bandit do? Sequential stopping works well along the sample dimension, and we include it as a baseline. It cannot, however, choose a thinking cap before generation begins. Under a shared batch budget, it also has no global price telling it when a question should never be started. DIPA itself names the thinking-token dimension as open. A hybrid is also possible, with the hull choosing the cap and sequential stopping choosing the count. We test this hybrid rather than assuming one approach dominates.

Why not just route questions into three hand-tuned tiers? Learning How Hard to Think found tiers more robust than fine-grained online allocation, so a tuned three-tier policy is a serious competitor. Our hypothesis is that hull allocation with shrinkage produces a similar small set of operating points, but chosen per question. We report both methods against a tier policy whose tier boundaries and budgets are tuned on the same held-out split. If tiers match hull allocation, the honest conclusion is that the hull mainly explains why binning works.

Why not just train the model to think less, as DRQA does? Training for conciseness shifts every question's curve to the left but still applies the same rule to all of them. DRQA reports that extreme compression hurts the hardest problems, which is exactly where allocation matters. We therefore treat DRQA as complementary and run our allocator on top of a concise model as well.

Decisive Experiments

The benchmarks are GSM8K, MATH-500, AMC 2023 and AIME 2024 for math, and LiveCodeBench for code, where unit tests act as the verifier. We use an 8B open distilled reasoning model of the kind DRQA evaluates, plus Qwen2.5-1.5B-Instruct to connect with Latency and Token-Aware Test-Time Compute. The metrics are accuracy at matched total generated tokens, the full accuracy-versus-token curve, and the fraction of the gap between uniform and oracle allocation that each method closes.

Check 1: are the curves non-concave? Stage 1 reports the share of questions with non-concave thinking-length curves and their share of solvable accuracy. If that share is near zero, the central claim is falsified.

Check 2: does the allocation rule matter by itself? On oracle curves, we compare hull and greedy allocation at budgets from 10% to 100% of the uniform-best budget. The gap should concentrate in mid-range budgets and on AIME- and AMC-level questions.

Check 3: does the gain survive prediction noise? With learned and training-free curve predictors, hull allocation with shrinkage should beat both online greedy allocation and three-tier binning on MATH-500 and LiveCodeBench, the setting where binning previously won.

Check 4: does deliberate dropping pay off? Following the video admission result, we measure how many questions are skipped at each budget. We also verify that removing the skip option lowers total accuracy at tight budgets.

For context, the file has no reported allocation result on NuminaMath-CoT, TACO or GPQA-Diamond. We therefore do not use those as headline comparisons.