← All AI/ML open problems

Verification & proof search · Statistical learning theory / Open question

Compute-Optimal Theorem Proving

Proof-agent coordination spends compute on a changing set of interdependent obligations, where a shared lemma can help several possible root proofs.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

On a finite acyclic AND–OR proof graph with NN nodes, let solver calls have costs in [cmin⁡,cmax⁡][c_{\min},c_{\max}] and unknown node-dependent success probabilities; completed lemmas can be reused by all parents. Under budget CC, bound VC⋆−VCπ^V_C^\star-V_C^{\hat\pi}, where VCπV_C^\pi is root-proof success and the comparator knows the call distributions but not future outcomes. Determine how graph sharing and the cost of estimating solver quality change achievable regret and matching lower bounds.

Assumptions and scope

  • Begin with a declared graph class and stochastic solver model, including dependencies, interruption/resumption costs and whether outcomes are independent conditional on latent task type.
  • Use a nonclairvoyant distribution-informed scheduler with the same available solvers and budget as comparator; do not compare against an oracle that knows future random outcomes.
  • Keep proof correctness separate from estimates of completion probability. If graph revision or solver improvement is allowed, specify its observation/cost model as an extension.

What would settle it?

A cost-normalized competitive, regret or approximation guarantee and matching lower bounds for the declared shared-subgoal class, with an explicit extension or obstruction for revisable graphs.

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

Maestro implements global coordination; LEVER optimizes costs during AND/OR search; Sonoda et al. bound finite-budget provability for offline value learning and greedy proving. The target adds online allocation under unknown costs and reusable lemmas. A finite-horizon theorem does not decide unrestricted provability. 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

  1. Li et al. — Maestro: Agentic Formal Proof Development by Coordination ↗related algorithm · source checked 2026-11-19

    Full-text methods previously inspected: structured failure reports, global plan mutation and asynchronous workers; performance gains do not by themselves establish scheduler regret bounds.

  2. Jain et al. — LEVER: Adaptive Cost-Aware Proof Search Over AND/OR Graphs ↗related algorithm · source checked 2026-11-19

    Abstract checked: programmable objectives and cost-aware partial-proof scoring are existing methods. The proposed target concerns guarantees with unknown, changing shared-subgoal costs.

  3. 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.

  4. Sonoda, Akiyama and Uezato — Why Agentic Theorem Prover Works: A Statistical Provability Theory of Mathematical Reasoning Models ↗partial theory · source checked 2026-11-19

    Publisher abstract checked: finite-horizon reachability MDP, offline action-value regression and greedy proving; occupancy-weighted error bounds involve truncated proof length, coverage and label noise. Budget-limited success must not be equated with unrestricted syntactic provability.