PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theory of Inference Compute Scaling: Reasoning through Directed Stochastic Skill Search

Austin R. Ellis-Mohr, Anuj K. Nayak, Lav R. Varshney

arXiv:2507.00004v2cs.LGcs.AIcs.CYcs.PF

TL;DR

Inference is becoming a major and growing component of LLM resource use, but existing compute-optimality analyses do not fully integrate training, model size, data, and inference strategy. The paper introduces DS3, a stochastic skill-graph framework with tractable cost and success analyses, and shows that it recovers linear accuracy scaling with logarithmic training and inference compute and tokens.

  • Problem

    Inference energy and compute can substantially outweigh training over deployed model lifetimes, motivating compute-scaling analyses that account for this recurring burden.

    Source: §I · p. 1

  • Method

    DS3 models inference as stochastic traversal over directed latent skill graphs and derives analytical behavior for sequential and branching strategies under simplifying assumptions.

    Source: §II · p. 7, A. Idealized Setup · p. 8

  • Results

    Accuracy scales linearly with the logarithm of training compute, inference compute, and tokens used.

    Source: 1) Accuracy Scaling with Training and… · p. 18

  • Takeaways & Limitations

    The framework supports codesign and resource allocation across training and inference by linking inference dynamics, training structure, and task difficulty.

    Source: §V · p. 30

Abstract

from arXiv · show

Large language models (LLMs) demand considerable computational, energy, and financial resources during both training and deployment. While scaling laws for training have guided much of the field's recent progress, inference costs now represent a significant and growing component of the overall resource burden, particularly for reasoning-focused models. Existing characterizations of compute-optimality that consider model size, dataset size, and inference tokens in isolation or in fixed combinations risk overlooking more efficient operating points. We introduce directed stochastic skill search (DS3), a general framework that represents inference as stochastic traversal over a learned skill graph. From a simplified yet expressive instantiation, we derive closed-form expressions for task success and compute cost across a wide range of inference strategies -- including chain-of-thought (CoT) and tree-of-thought (ToT) -- enabling comparative analysis as a function of task difficulty and model capability. To that end, we extend a prior first-principles tripartite graph framework of LLM training to incorporate inference, and separately bridge DS3 with empirical methods that characterize LLM scaling behavior. We theoretically recover empirically observed patterns, including: linear accuracy scaling with logarithmic compute; variation in preferred inference strategies as a function of task difficulty and model capability; emergent behavior elicited by reasoning even when performance plateaus under parameter scaling; and both best-of-N (BoN) and majority voting behavior captured within a unified analytical framework. By explicitly characterizing training-inference interdependencies, our framework deepens theoretical understanding and supports principled algorithmic design and resource allocation.

I. INTRODUCTION

The paper motivates compute scaling as a coupled training–inference problem: inference costs are increasingly consequential, while model size alone does not reliably predict task accuracy or efficient deployment. It situates this problem across games, LLM training, inference strategies, and compute-optimal allocation.

I. INTRODUCTION

  • Inference can dominate operational resource use despite falling unit costs, because usage, task length, and reasoning demand continue to grow.Reported inference shares include 60% of machine-learning energy use at Google and 65% for Meta’s LLM; production-scale usage can make inference outweigh training.Source: §I · p. 1

A. Games

  • Game systems illustrate the evolving training–inference division, from Deep Blue’s brute-force search to AlphaGo’s learned generation, verification, and tree search.AlphaGo achieved superhuman Go performance while evaluating orders of magnitude fewer positions than Deep Blue, and AlphaGo Zero exposed a gap between raw-network and search-augmented performance.Source: A. Games · p. 2

B. LLM Training Scaling

  • Hierarchical skill structure has been used to explain emergent capabilities, performance plateaus, and training-compute-optimal scaling as model size changes.The framework treats concept acquisition as iterative peeling over prerequisite skills and uses random-graph tools to characterize skill emergence.Source: B. LLM Training Scaling · p. 2

1) Pretraining Loss vs. Task Accuracy:

  • Pretraining loss does not directly determine downstream task accuracy, motivating task-level analysis and two-step mappings from loss to performance.Downstream accuracy can plateau, saturate, or even worsen while loss improves, and two-step methods commonly fit loss before applying a sigmoid or decaying-exponential task mapping.Source: 1) Pretraining Loss vs. Task Accuracy · pp. 3–4

C. LLM Inference Scaling

  • Inference scaling includes sequential CoT, parallel BoN or majority voting, and hybrid ToT, whose best balance depends on model capability, task difficulty, and computational constraints.CoT can elicit capabilities under otherwise flat scaling, while ToT tends to benefit harder tasks and weaker models more strongly.Source: C. LLM Inference Scaling · p. 4, 1) Pretraining Loss vs. Task Accuracy · p. 4

D. Compute-Optimality

  • Inference scaling changes compute-optimal design because total-lifecycle objectives can favor smaller models trained on more data than Chinchilla-style training-only choices.Prior total-compute analyses focus on pretraining loss, while inference-aware allocation must account for recurring deployment costs and hardware or algorithmic characteristics.Source: D. Compute-Optimality · p. 5, 1) Training Compute · p. 5

1) Training Compute:

  • Training-compute analysis favors a proportional Chinchilla relationship between parameter count and training tokens, with the token-to-parameter ratio estimated near 20 and later suggested closer to 25.Source: 1) Training Compute · p. 5

2) Inference Compute:

The paper formalizes inference as directed stochastic traversal over latent skills and uses this framework to compare inference strategies and their costs. It connects these analyses to total-compute allocation and empirical scaling phenomena.

3) Total Compute:

  • The framework supports joint optimization of model size, training data, and inference strategy under flexible total-compute constraints, beyond objectives that minimize pretraining loss alone.Prior allocation studies omit explicit inference scaling, while algorithmic and hardware choices can alter the resulting optimum.Source: 3) Total Compute · p. 6

E. From Empirical Findings to Theoretical Foundations

  • Closed-form analyses recover linear accuracy scaling with the logarithm of training compute, inference compute, and generated tokens.The framework is presented as theoretically grounded and aligned with empirical scaling regularities.Source: E. From Empirical Findings to… · p. 6

F. Contributions and Outline

  • The paper compares CoT and ToT as task difficulty changes and shows that context-length constraints affect their relative efficiency.Its broader outline also covers emergent capabilities, repeated sampling, energy considerations, forecasting, and security implications.Source: F. Contributions and Outline · pp. 6–7, 2) Inference Compute · p. 6

II. DIRECTED STOCHASTIC SKILL SEARCH

  • DS3 represents each inference trace as a stochastic walk on a directed latent skill graph with skill nodes and control nodes for branching, idling, and termination.The graph may differ across traces, allowing heterogeneous inference topologies within an ensemble.Source: §II · p. 7
  • DS3 assigns stochastic transition and outcome processes to traces while allowing evaluation and cost functions to depend on histories, ensemble behavior, and the external environment.Costs can represent per-step compute or latency as well as global contention, coordination, energy pricing, and hardware efficiency.Source: §II · pp. 7–8

A. Idealized Setup

The idealized DS3 setup models inference over a shared skill graph with directed stochastic transitions, while the CoT specialization derives task completion and token usage under capped budgets.

A. Idealized Setup

  • DS3 analyzes CoT, ToT(1), BoN, and MV on a fully connected graph partitioned into required, relevant-but-not-required, and irrelevant skills.Task completion requires sequential execution of m required skills, with the complete relevant set having cardinality M.Source: A. Idealized Setup · p. 8
  • Directionality δ ranges from an undirected random walk at δ = 0 to a perfectly directed walk at δ = 1 toward the next required skill.The corresponding directionality parameter ˆι quantifies the bias toward selecting the correct next skill.Source: A. Idealized Setup · pp. 8–9
  • The setup assumes uniform, history-independent skill success probability p, perfect memory, no maximum context length, and no early termination for incorrect answers.These assumptions favor longer sequential chains, while context-length penalties and ordered completion can disadvantage sequential strategies.Source: A. Idealized Setup · pp. 8–9

B. CoT

  • CoT is a single sequential trace whose effective probability of selecting and executing the next required skill is ˆιp.The number of steps to first succeed in this combined action is geometrically distributed, and completing m skills requires m independent geometric successes.Source: B. CoT · p. 9
  • Under a capped budget, CoT task completion follows a negative-binomial model, while tractable piecewise-linear and Gaussian approximations preserve linear-growth and saturation trends.The expected token output uses the capped expected steps, with the Gaussian approximation applied in a central region and limiting behavior handled in the tails.Source: B. CoT · pp. 10–11

C. ToT(1)

ToT(1) is a hybrid sequential-parallel strategy that branches after skill visits and uses an evaluator to select among traces, increasing per-step success through concurrent exploration.

C. ToT(1)

  • ToT(1) branches immediately after a skill node, and an oracle evaluator selects a successful trace or terminates the alternatives.If exactly one trace succeeds it is selected; otherwise all but one are terminated arbitrarily.Source: C. ToT(1) · p. 11
  • With b concurrent branches, the probability of successfully locating and executing a required skill in one step becomes 1 − (1 − ˆιp)^b.Branching therefore changes the effective per-step success probability while retaining sequential completion across required skills.Source: C. ToT(1) · p. 11
  • For total step budget Tmax, ToT(1) provides only ⌊Tmax/b⌋ effective sequential skill steps because each step evaluates b nodes.Its expected token usage and inference cost account for b concurrent branches of length ⌊Tmax/b⌋.Source: C. ToT(1) · p. 11

E. MV

The DS3 analysis compares majority voting and sequential-to-branching inference under compute constraints, showing that preferred strategies depend jointly on task difficulty, model capability, task length, and branching. It also identifies distinct high- and low-capability regimes and motivates adaptive strategy selection.

E. MV

  • Majority voting defines success as the correct output receiving more votes than any incorrect alternative, with ties resolved randomly, while its expected token usage and inference cost match BoN.The output distribution is multinomial over k samples, with one probability assigned to the correct answer and the remainder to incorrect outputs.Source: E. MV · p. 12

F. Balance Between Sequential and Parallel Reasoning

  • ToT(1) can generate more tokens under a fixed compute budget, and the attainable token count increases with branching factor because parallel strategies reduce the impact of quadratic attention costs.The comparison is illustrated by token-budget curves for CoT and ToT(1) across branching factors.Source: F. Balance Between Sequential and… · p. 12, Figure 4 · p. 13
  • Figure 5 shows ToT(1) favored at low per-step success probabilities, CoT favored at high probabilities, and intermediate preferences determined by required skills and branching factor.The figure compares branching factors 4 and 16, with white regions marking near-equal performance or invalid comparisons.Source: Figure 5 · p. 13, F. Balance Between Sequential and… · pp. 13–14
  • The preferred inference strategy varies with per-step success probability, task length, branching factor, and token budget, with crossover behavior between CoT and ToT(1).Theorem 1 and the associated conjecture characterize CoT as preferred above a capability-dependent crossover and ToT(1) below it, with ToT(1) winning for sufficiently large tasks at fixed low capability.Source: F. Balance Between Sequential and… · p. 14
  • In the high-capability regime, CoT minimizes output tokens and is optimal when the model reliably completes each sequential skill step.This conclusion follows from the b = 1 case, where sequential reasoning avoids the additional branching cost.Source: F. Balance Between Sequential and… · p. 14
  • In the low-capability regime, ToT(1) provides a multiplicative success-probability gain proportional to b^m/2 when each branch can complete at least m steps.The result applies when the compute budget supports the required depth on every branch.Source: F. Balance Between Sequential and… · p. 14
  • Complete fatigue makes parallelization strictly better: with first-step success r1, b traces achieve 1 − (1 − r1)^b > r1 for b > 1 and 0 < r1 < 1.This stylized case shows how temporal degradation can reverse the preference for sequential reasoning and supports adaptive strategies.Source: F. Balance Between Sequential and… · pp. 14–15
  • Longer reasoning chains trade reduced per-step difficulty against compounded error, creating tension between solution depth and cumulative risk.The framework connects this tension to hierarchical task completion using either a few complex skills or many simpler ones.Source: F. Balance Between Sequential and… · p. 15

III. UNIFYING TRAINING AND INFERENCE SCALING IN LLMS

The paper unifies training and inference scaling by extending a hierarchical tripartite skill graph with flexible traversal and task-distribution averaging. The resulting framework links concept acquisition, skill composability, inference success, and compute allocation while refining acquisition behavior to match empirical Chinchilla trends.

III. UNIFYING TRAINING AND INFERENCE SCALING IN LLMS

  • A task-distribution formulation averages per-task success and inference cost over skill difficulty and the number of required skills.This avoids analyzing a single task in isolation and defines expected accuracy and compute as weighted sums over tasks.Source: §III · p. 15

A. Hierarchical Skill-Text Tripartite Graph Framework for LLM Training

  • DS3 extends a hierarchical text–concept–skill graph with upward and downward traversal, allowing tasks to be solved through decomposition, compression, or prerequisite-based composition.The framework retains hierarchical skill acquisition while supporting flexible problem-solving strategies during inference.Source: A. Hierarchical Skill-Text Tripartite… · p. 15, Figure 6 · p. 16
  • The model acquires concepts from text, maps them to skills, and recursively builds higher-level skills from prerequisites across the hierarchy.More text and parameters expand the learned concept set and the breadth and depth of acquired skills.Source: Figure 6 · p. 16, A. Hierarchical Skill-Text Tripartite… · pp. 16–17
  • The acquisition mechanism is modified to depend directly on learned concepts, ensuring that fixed-compute performance declines monotonically away from the Chinchilla-optimal token-to-parameter ratio.The change addresses cases where co-occurrence-based acquisition incorrectly predicts improved accuracy away from the optimum.Source: A. Hierarchical Skill-Text Tripartite… · pp. 16–17
  • Training-compute optimization recovers equal scaling of parameters and data and the Chinchilla rule, while inference success requires composable skills to be located and executed within the skill graph.Skill-layer composability is associated with emergence of a giant connected component when expected degree exceeds one.Source: A. Hierarchical Skill-Text Tripartite… · pp. 17–18
  • The acquisition analysis does not apply in the overparameterized regime because its finite blocklength approximation fails beyond the Chinchilla-optimal data-per-parameter ratio.The paper notes that this regime is outside the current scope.Source: A. Hierarchical Skill-Text Tripartite… · p. 17

1) Accuracy Scaling with Training and Inference Compute:

The empirical comparisons use interpretable simulations calibrated to Claude 3.7 Sonnet and OpenAI’s o1 on AIME. They show that accuracy scales approximately linearly with the logarithm of training compute, inference compute, and tokens, while optimal allocation shifts with downstream task load.

1) Accuracy Scaling with Training and Inference Compute:

  • The simulations use rounded parameters and public benchmark discussions to compare task-level behavior for Anthropic’s Claude 3.7 Sonnet and OpenAI’s o1 on AIME.The setup is intended to match qualitative features without overfitting.Source: 1) Accuracy Scaling with Training and… · p. 18
  • Larger downstream task loads favor allocating proportionally more compute to pretraining because its cost is amortized across tasks.The preferred allocation depends on the task mix for general-purpose language models.Source: 1) Accuracy Scaling with Training and… · p. 18
  • Accuracy scales linearly with the logarithm of training compute, inference compute, and tokens across the reported Claude 3.7 and o1 comparisons.These results are presented as empirical regularities predicted by the DS3 framework.Source: 1) Accuracy Scaling with Training and… · p. 18

B. Downstream Empirical Fitting Method

The empirical fitting method maps pretraining loss to skill proficiency and then evaluates DS3 inference scaling under simplifying assumptions. The analysis identifies joint training–inference efficiency gains and shows that reasoning depth can amplify model-size scaling, especially for difficult skills.

B. Downstream Empirical Fitting Method

  • The empirical method maps pretraining loss to skill proficiency through a sigmoid functional ansatz, then uses DS3 to simulate downstream inference scaling.Its qualitative conclusions assume monotonic improvement of skill success with training and meaningful DS3 representation of inference scaling.Source: B. Downstream Empirical Fitting Method · pp. 18, 20
  • The empirical fitting analysis focuses on a regime where overtraining smaller models continues improving downstream performance and leaves saturation or degraded transferability for future work.It also omits multiple solution strategies, prerequisite structures, and attention-related inference costs.Source: B. Downstream Empirical Fitting Method · pp. 18, 20

1) Efficiency Benefits of Explicit Token Scaling:

  • Jointly optimizing model size, dataset size, and inference-token budget accesses more efficient regimes than restricting scaling to a Chinchilla-optimal training plane or another two-dimensional slice.The synthetic analysis identifies substantial inefficiency from those lower-dimensional constraints.Source: Figure 8 · p. 20, 1) Efficiency Benefits of Explicit… · p. 21
  • More complex tasks require higher base-model capability and larger models but benefit primarily from inference-token scaling, whereas simpler and moderately difficult tasks scale with both parameters and tokens.In the inference-compute-optimal regime, dataset size does not affect cost.Source: 1) Efficiency Benefits of Explicit… · p. 21, Figure 9 · p. 21

C. Can Reasoning Elicit Emergence?

  • For difficult skills, increasing reasoning depth can amplify the model-size scaling slope by an arbitrarily large factor, while skills with r ≥ 1/2 receive no slope boost although accuracy still increases.The theorem analyzes reasoning depth when low-depth accuracy has plateaued at small per-step success probability.Source: C. Can Reasoning Elicit Emergence? · p. 22

1) Interpretation and Mechanisms:

The framework explains how reasoning depth can improve performance after model-size plateaus and unifies BoN and MV behavior through task-level success distributions. It also connects these analytical forms to empirical pass@k fits and inferred search directionality.

1) Interpretation and Mechanisms:

  • Deeper reasoning can improve task success and make accuracy more responsive to model size even when performance has plateaued.The framework identifies model-size-to-skill mapping, skill-count bottlenecks, and task decomposition as mechanisms supporting these gains.Source: 1) Interpretation and Mechanisms · pp. 22–23
  • Reasoning produces smooth or step-like emergence depending on whether task difficulties are broadly distributed or clustered.Additional reasoning can enable smaller models to solve tasks that otherwise remain unsolvable.Source: 1) Interpretation and Mechanisms · p. 23

D. BoN Coverage and MV Saturation

  • BoN accuracy increases monotonically with sample count and approaches one as the number of samples grows.This follows from the probability that at least one correct answer appears among independent samples.Source: D. BoN Coverage and MV Saturation · p. 23
  • Unlike BoN, MV can saturate early because it requires the correct answer to become the majority rather than merely appear among sampled outputs.For heterogeneous task populations, continued sampling benefits BoN while MV may stop improving early.Source: D. BoN Coverage and MV Saturation · p. 23
  • A Beta-mixture success model with an unsolvable-task point mass closely matches empirical pass@k curves and reveals many low-success tasks plus a high-success mode for Llama-3-70B-Instruct.The fitted framework also carries BoN parameters into MV fitting without additional tuning.Source: D. BoN Coverage and MV Saturation · pp. 24–25, Figure 10 · p. 24
  • The framework infers higher search directionality for instruction-tuned models, although the estimate depends on strong task-distribution assumptions and lacks thorough robustness analysis.The inference uses a two-mode Gaussian task prior and excludes alternative solution strategies.Source: D. BoN Coverage and MV Saturation · pp. 25–26

A. Distinct Energy Profiles

Inference has distinct energy, hardware, and governance constraints from training, with costs shaped by latency, memory, context length, and deployment conditions. These differences motivate inference-aware algorithmic design, capability measurement, security analysis, and system-level planning.

A. Distinct Energy Profiles

  • Training and inference have asymmetric computational economics, so inference tokens cannot be treated as equivalent to training tokens for resource allocation.Inference also runs throughout deployment, while training is largely a one-time expenditure.Source: A. Distinct Energy Profiles · p. 26

1) Usage and Deployment Environments:

2) Algorithms and Hardware:

  • Inference methods trade resource profiles differently: CoT increases context and KV-cache demands, parallel MV benefits from batching, and ToT prunes pathways to control costs.Latent-space reasoning and speculative decoding are additional approaches to reducing context or latency costs.Source: 2) Algorithms and Hardware · p. 28

B. Capability Forecasting

  • Compute-based oversight remains difficult because compute is inconsistently measured, decentralized, and increasingly decoupled from deployment through distillation and edge hardware.These conditions reduce transparency and complicate monitoring and attribution.Source: B. Capability Forecasting · p. 29
  • Training-only compute thresholds can underestimate capabilities because inference compute also contributes to performance; the paper proposes COOM = a log(Ctr) + b log(Cinf).Including inference compute is presented as a fuller capability measure for governance.Source: B. Capability Forecasting · p. 29

C. Security

  • Inference scaling may accelerate automated research and improve planning and code synthesis, while also increasing misuse risks in cybersecurity and biosecurity.Security-relevant deployment still faces unresolved tradeoffs among capability, interpretability, and responsiveness.Source: C. Security · pp. 29–30

V. CONCLUSION

  • The framework represents security-relevant behavior as acquired skills or transitions, providing a basis for analyzing how security outcomes scale with inference-time capabilities.The conclusion calls for codesign across training, inference, algorithms, hardware, and deployment policy.Source: C. Security · p. 30, §V · p. 30

APPENDIX A ADDITIONAL ANALYSIS FOR COT VS. TOT(1) INFERENCE POLICIES

The appendices derive and numerically analyze inference-policy and compute-allocation behavior within the DS3 framework. They compare CoT and ToT(1), fit skill-based scaling to Claude 3.7 and o1, and characterize inference-compute-optimal allocation across task difficulties.

B. Numerical Analysis

  • The ToT(1) cost includes attention, logit accumulation, and branch-comparison terms, while verification is treated as negligible under an oracle-verifier assumption.The numerical setup uses a 200-token prompt, a 10-billion-parameter model, 96 layers, attention dimension 12,288, and 25 tokens per branch allocation.Source: B. Numerical Analysis · p. 37
  • CoT and ToT(1) have narrow success transitions, with comparative gains sensitive to task difficulty, branching strategy, and matched token budgets.Fig. 13 reports CoT and ToT(1) heatmaps across per-step probabilities and branching factors 4 and 16.Source: B. Numerical Analysis · p. 37, Figure 13 · p. 38

Claude 3.7 Sonnet Fit

  • Claude 3.7 and OpenAI o1 fits use simplified Chinchilla-style dense-pretraining assumptions to illustrate qualitative scaling structure rather than architectural specifics.The Claude fit uses κ = 20 and task-dependent skill parameters, while the o1 fit uses reported training compute and a 64,000-token inference budget.Source: Appendix B · p. 38, Claude 3.7 Sonnet Fit · p. 38, OpenAI o1 Fit · p. 39

Solution Strategy Layer Selection

  • The layer-selection strategy maximizes expected accuracy under a maximum step budget, but mixing layers, adaptive inference, and minimizing expected steps remain alternative objectives.The analysis notes that lower layers may offer partial progress even when they cannot fully solve highly compositional tasks.Source: Solution Strategy Layer Selection · p. 39

APPENDIX C TWO-STEP FORECASTING METHODS: ADDITIONAL DETAILS

  • Global accuracy optimization can diverge from Chinchilla or fixed-token constraints, producing resource-allocation gaps and inefficiencies across matched compute budgets.Fig. 8 compares unconstrained and Chinchilla trajectories, while Fig. 15 reports significant inefficiencies under fixed token restrictions.Source: Appendix C · p. 40, Figure 15 · p. 40

A. Infinite Training Data Regime

  • Across task difficulties, inference-compute-optimal fits show mean parameter and token scaling exponents of 0.367 and 0.640, respectively, with median R2 values of 0.998 and 0.999.Out of 10,000 fits, 9,980 parameter fits and 9,871 token fits passed the stated threshold.Source: A. Infinite Training Data Regime · p. 41
  • A representative inference-compute-optimal fit allocates compute with log10(N) = 0.28 log10(Cinf)+5.60 and log10(Ω) = 0.72 log10(Cinf)−5.90.For the illustrated task, the fits have R2 = 0.95 for model size and R2 = 0.99 for inference tokens.Source: Figure 16 · p. 41

APPENDIX D SUPPLEMENTAL INFORMATION: CAN REASONING ELICIT EMERGENCE?

  • The supplementary emergence derivation evaluates a limiting form by logarithmic transformation, L’Hôpital’s Rule, and exponentiation.The appendix states that this limit is used in Proof 2 but does not provide the resulting expression in the supplied passage.Source: Appendix D · pp. 41–42

APPENDIX E BEST OF N AND MAJORITY VOTING

This appendix derives the asymptotic behavior of best-of-N coverage under a Beta-distributed success rate. The resulting leading-order improvement follows a power law in the number of samples.

APPENDIX E BEST OF N AND MAJORITY VOTING

  • The appendix connects the asymptotic BoN result to a broader DS3 treatment of pass@k and majority voting under idealized task-success distributions.It also describes a push-forward distribution relating skill levels and required skills to pass@k.Source: Appendix E · p. 42

A. Asymptotic Behavior of BoN Accuracy

B. BoN Model Fit

The appendix fits an analytically motivated BoN coverage curve to observed pass@k values and derives a majority-vote saturation model. The majority-vote limit is controlled by the Beta prior and the largest incorrect-output weight.

B. BoN Model Fit

  • The BoN fitting procedure minimizes mean squared error under α > 0, β > 0, and 0 < A ≤ 1 using L-BFGS-B, but is descriptive rather than predictive.The fitted curve is used to interpolate observed pass@k values, not for inference beyond those observations.Source: B. BoN Model Fit · p. 44

C. Derivation of the Majority-Vote Saturation Formula and Fitting

  • Majority voting succeeds asymptotically when the correct-label probability exceeds the largest weighted incorrect-label probability, with threshold rc = c*/(1 + c*).The threshold follows from the assumed error spectrum qj(ψ) = (1 − ψ)cj.Source: C. Derivation of the Majority-Vote… · p. 44
  • The limiting majority-vote success probability is expressed through the regularized incomplete Beta function evaluated at rc.The Beta CDF supplies Pr[ψ ≤ rc], which determines the asymptotic failure contribution.Source: C. Derivation of the Majority-Vote… · p. 45
  • The fitted c* is determined from the empirical plateau and previously fitted Beta prior, binding the largest single error weight to observed saturation.A truncated geometric spectrum then supplies the remaining incorrect-output weights.Source: C. Derivation of the Majority-Vote… · p. 45
  • The majority-vote evaluation assumes an alphabet of size |Y| = 10 and uses 10,000 Monte Carlo samples per point without studying extrapolation.Uniform tie-breaking is used when the correct label shares the maximum vote count.Source: C. Derivation of the Majority-Vote… · pp. 44–45

D. Push-Forward Skill Distribution to Estimate Search Directionality

The appendix estimates search directionality by pushing a simplified task distribution through the DS3 success mapping and fitting model-specific parameters to pass@k data. It also tabulates model and effective reasoning-step budgets used for empirical fits.

D. Push-Forward Skill Distribution to Estimate Search Directionality

  • Search directionality is estimated by assuming a two-mode task distribution over required reasoning steps and mapping skill difficulty through an idealized CoT DS3 success model.The step distribution places mass at m = 1 and m = 100, while the model uses a Chinchilla-style loss-to-sigmoid mapping.Source: D. Push-Forward Skill Distribution to… · p. 45
  • The two-mode Gaussian is a simplifying approximation that captures important distributional features but may be extended using larger per-trial token budgets.The appendix states that the assumption is not necessary and that multiple solution strategies are excluded.Source: D. Push-Forward Skill Distribution to… · pp. 45–46
  • Because the difficulty-to-success map is strictly monotone for fixed m, a change-of-variables formula produces the pushed-forward success distribution.Model-specific directionality parameters are then jointly optimized by maximum likelihood on observed pass@k samples.Source: D. Push-Forward Skill Distribution to… · pp. 45–46

Tabulated Parameters for Models Considered

  • Table II records model parameters, training-data sizes, estimated Chinchilla losses, and maximum reasoning steps derived from available output budgets.The effective step budget divides the output budget by ω = 25 tokens per skill step.Source: Tabulated Parameters for Models… · p. 46, Table II · p. 46
Loading 2507.00004v2…