Statistical learning theory · Verification & proof search / Open question
Measuring the Limits of Reasoning
Claims of a broadened reasoning boundary depend strongly on rare successes, prompt heterogeneity and the evaluation budget.
Seed catalog · Showing the bundled record.
Problem statement
Compare for two policies on independent prompts, using conditionally independent Bernoulli rollouts with adaptively chosen depths. For each policy allow an atom at and require for , with fixed . Determine minimax confidence width at total rollout budget when exceeds individual sampling depths, and whether adaptive depths improve on fixed-depth designs. Correlated tree search requires a separate estimand and is not covered by this Bernoulli target.
Assumptions and scope
- For the independent-rollout starting model, define the prompt distribution, policy and Bernoulli sampling protocol; treat tree-search success as a different estimand.
- Any near-zero-tail restriction on success probabilities must be stated and its necessity tested. Unrestricted large-K extrapolation from fixed-depth counts is known not to be identifiable.
- Separate uncertainty over prompts from uncertainty over repeated rollouts, and require validity under the declared adaptive stopping rule. Paired comparison of two policies may share prompts but not assume shared rollouts.
What would settle it?
Matching upper and lower bounds on the comparison error or identified-set width for a declared tail class as a function of total rollout budget, together with an adaptive allocation rule attaining them, or a lower bound showing that adaptivity cannot improve on fixed depth in that class.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Singh and Singh already characterize the fixed-n identified set and show generic k>n extrapolation is unidentified; Kazdan et al. already propose beta-binomial forecasts with dynamic budget allocation; per-task confidence composition exists. The residual target is minimax theory for adaptive depths, two-policy comparison and correlated search. It is not a claim that ordinary binomial intervals or fixed-n identifiability are open. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Singh and Singh — What Fixed-Rollout pass@k Evaluations Can Identify ↗partial theory · source checked 2026-11-19
Abstract checked: in the pooled conditional-Binomial model, fixed-n counts identify only n moments, so generic pass@k for k>n is not identified; sharp identified intervals and a finite-task certificate are given. Adaptive per-task budgets and search-based estimands are outside that fixed-n baseline.
- Kazdan et al. — Efficient Prediction of Pass@k Scaling in Large Language Models ↗related algorithm · source checked 2026-11-19
Abstract checked: beta-binomial estimation from limited samples and a dynamic sampling strategy giving harder problems more budget. These are existing parametric-forecast and allocation methods, not minimax guarantees.
- Cheng et al. — How RL Reshapes LLM Reasoning: Transferability, Coverage, and Scaling Laws ↗partial theory · source checked 2026-11-19
Full-text model and theorem statements checked: two-stage linear softmax policies with frozen features, realizability/orthogonality assumptions and gradient-flow limits. Coverage can change without new strategy support.
- Schnitzer et al. — Probabilistic Performance Guarantees for Multi-Task RL ↗partial theory · source checked 2026-11-19
Abstract checked: composition of per-task finite-rollout confidence bounds with task-level generalization is existing theory.
- Yu et al. — Difficulty-Adaptive Tree-Structured Policy Optimization ↗related algorithm · source checked 2026-11-19
Publisher abstract checked: sentence-entropy branching, adaptive difficulty and sibling-diversity advantages. Finite-budget empirical coverage gains do not imply independent-rollout statistics.