acceptodds
Under review as a conference paper at ICLR 2027

Are hidden constants in theoretical computer science really that large?

Abstract

We use large language models to recover the hidden constants in theoretical computer science proofs, asking how large the constants are, why some become large, and how tighter analysis can improve the guarantees. We introduce ConstAble, which follows proof dependencies to derive explicit bounds and track their conditions. Our benchmark, ConstEval, evaluates bound recovery, proof validity, and error detection on 93 prepared instances and 93 paired variants with injected proof defects. Among 91 targets with numerical coefficients, 69 have representative coefficients below 1,000 under their stated resource models and parameter settings. The recovered proofs show how costs multiply across nested calls and why small leading coefficients can hide large costs at finite input sizes. The resulting bounds support comparisons at concrete input sizes, and our subsequent analysis tightens an earlier recovered three-distinctness bound without changing the algorithm. ConstAble improves bound completion over one-shot inference. With comparable median token use, it completes 65.6%–92.5% of targets, while baselines using additional generation or revision complete at most 9.68%.

Primary area:
datasets and benchmarks
Keywords:
hidden constant, theoretical computer science, proof map

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DYFvOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the recovery of hidden constants in asymptotic complexity bounds using LLMs. The authors introduce ConstAble, a structured pipeline that reconstructs explicit bounds by tracing proof dependencies and combining local quantitative derivations, and ConstEval, a benchmark of 93 recovery problems and 93 variants with injected proof defects.

ConstAble substantially outperforms one-shot and expanded-inference baselines, achieving completion rates of 58.1%--92.5%. The authors also analyze the recovered constants, finding that 69 of 91 numerical coefficients are below 1,000, while some are extremely large. Case studies illustrate how hidden constants arise and how explicit bounds can improve finite-size complexity analysis.

Critical strengths
  1. The paper addresses an important but relatively underexplored problem: recovering hidden constants that affect the practical significance of asymptotic complexity bounds. ConstEval provides a useful benchmark requiring both explicit numerical bounds and supporting mathematical derivations.
  2. The approach to recovering hidden constants through proof-dependency analysis is interesting. The improvements over the baselines demonstrate its effectiveness. The analysis of how large constants arise is also informative.
Critical weaknesses
  1. The correctness of recovered bounds is assessed mainly through LLM-based checks rather than formal verification. Although expert audits provide additional support, they cover only a subset of the results, and 23 of 381 initial judgments were overturned. Since the reported completion rates depend on the correctness of these assessments, their reliability remains a concern.
  2. The benchmark consists of selected, manually prepared proofs with limited external dependencies. This may exclude more complex cases where hidden constants are especially difficult to recover. It seems the finding that 76% of coefficients are below 1,000 may not generalize to theoretical computer science research more broadly.
Questions for authors
  1. How do the authors assess the reliability of LLM-based verification, particularly the possibility of systematic errors shared by generation and evaluation models?
  2. Given the dependence of constant magnitudes on resource models and normalization conventions, how broadly can the finding that 76% of coefficients are below 1,000 be generalized?
4 comments

Thank you for your careful review and for recognizing the additional support provided by our expert audits. We appreciate your questions about evaluation reliability and the scope of our findings on hidden constants. Below, we address your concerns and specific questions in turn.

How do the authors assess the reliability of LLM-based verification, particularly the possibility of systematic errors shared by generation and evaluation models?

Thanks for your question. We assess LLM-based verification through separate verifier sessions, a cross-verifier comparison on Qwen3.7 Plus and DeepSeek v4 Flash outputs, and expert audits of sampled verifier judgments.

1. Cross-Family Separation & Cross-Verifier Consistency (Appendix D.1)

For the Qwen3.7 Plus and DeepSeek v4 Flash experiments, generation and verification use different model families to reduce the risk of self-preference and shared model-family blind spots. To evaluate the sensitivity of our grading to the choice of verifier, we compared two frontier verifiers from distinct model families—Claude Opus 5.5 (xhigh) and GPT-6.1 Sol (ultra)—across 40 positive-instance outputs (i.e., outputs drawn from positive instances) generated by Qwen3.7 Plus (10 one-shot, 10 pipeline) and DeepSeek v4 Flash (10 one-shot, 10 pipeline).

The two verifiers reached identical verdicts on 39 out of 40 outputs (97.5%), showing high consistency across verifier choices on this sample.

The sole discrepancy occurred on the Qwen3.7 Plus pipeline output for Target [68] (Dijkstra's algorithm), where the target specification requires an explicit bound valid for all n≥1n \ge 1. The generated proof first derives a valid intermediate explicit bound holding for all n≥1n \ge 1, and then simplifies it into a final closed-form bound of 2496(m+nlg⁡n)2496(m + n \lg n) by invoking a threshold condition requiring n≥2n \ge 2. Claude marked the output Incorrect because the final reported expression omits the n=1n = 1 boundary case, whereas GPT marked it Correct because a valid bound covering all n≥1n \ge 1 was already explicitly established at an intermediate step and the final simplified coefficient is accurate under its stated n≥2n \ge 2 condition. This disagreement concerns how the rubric treats boundary coverage established in an intermediate step versus the final reported expression.

2. Derivation-Level Verification & Human Expert Audits (Section 4.1)

For both one-shot and pipeline runs, our task specification requires a complete, step-by-step quantitative derivation, including all lemma substitutions and premise checks (Section 2; Appendix G.1). Verifiers therefore assess explicit reasoning chains and the conditions supporting the resulting bounds. Every output on a positive instance is checked by two separate verifier agents running in fresh, isolated sessions: one checks proof validity and premise support, while the other checks quantitative expansion and domain coverage.

Domain experts audited 381 verifier judgments associated with sampled positive-instance outputs. They identified minor issues in 23/381 judgments (6.0%), mostly overly strict flags on loose but valid lemma bounds. All overall completion decisions for the affected outputs remained unchanged after expert adjudication.

The benchmark consists of selected, manually prepared proofs with limited external dependencies. This may exclude more complex cases where hidden constants are especially difficult to recover. It seems the finding that 76% of coefficients are below 1,000 may not generalize to theoretical computer science research more broadly.

Given the dependence of constant magnitudes on resource models and normalization conventions, how broadly can the finding that 76% of coefficients are below 1,000 be generalized?

We thank the reviewer for raising this point. The 69/91 proportion is descriptive of the retained corpus under its stated normalizations and parameter settings; it is not a population estimate for TCS. The scope and limitations of this corpus are discussed in §5.

Our benchmark construction (§2.1 and Appendix B.2) follows a two-stage protocol that combines topical diversity with verifiability. First, research-paper selection begins with stratified random sampling across major TCS conferences and journals spanning algorithms, complexity theory, and quantum computation. This provides coverage across different problem types and proof techniques. Second, we apply structural screening criteria: retained papers must provide complete proofs in the source PDF, unambiguous target parameterizations—for example, excluding O∗(⋅)O^*(\cdot) statements that suppress parameter-dependent factors—and at most three distinct substantive external results across the traced dependencies. We also exclude manuscripts longer than 50 pages because of the difficulty of constructing and exhaustively verifying their ground truth, as discussed in Appendix B.2. These criteria are based on proof accessibility and specification clarity, rather than on the recovered coefficient values. Across the 91 numerical targets, 69 representative coefficients fall below 1,000, giving 75.8%. The research-only proportion is similar: 48 of 65 numerical research targets, or 73.8%, have coefficients below 1,000.

Regarding resource models and normalization, each recovery target specifies the charged resource, growth term, parameter domain, and guarantee mode (§2). Appendix C.1 makes the coefficient-extraction rules explicit: parameter factors remain in the growth term, polynomial bounds use the largest coefficient among retained leading terms, and parameter-dependent coefficients are evaluated at stated admissible reference settings. Thus, the reported proportion characterizes the retained numerical targets under documented, target-specific conventions.

Applying the findings to another setting requires accounting for its resource units, normalization, and parameter choices. The accompanying full bounds retain parameter dependence, lower-order terms, and validity conditions, supporting concrete resource analysis beyond the summary statistic. Sections 3.2–3.4 illustrate how this information enables finite-size comparisons and reveals how resource requirements change with accuracy, success guarantees, and other problem parameters.

The correctness of recovered bounds is assessed mainly through LLM-based checks rather than formal verification. Although expert audits provide additional support, they cover only a subset of the results, and 23 of 381 initial judgments were overturned. Since the reported completion rates depend on the correctness of these assessments, their reliability remains a concern.

We appreciate the reviewer’s attention to our evaluation protocol. As discussed in Section 4.1, the majority of the 23 flagged cases among the 381 sampled verifier judgments involved the verifier being overly strict—for example, objecting to a valid but non-tight lemma bound that still sufficed to derive the target, or treating a source-paper typo as an error in the assessed proof.

Two examples illustrate the nature of these local assessment errors:

  • 59: A Nearly Optimal Discrete Query Quantum Algorithm for Evaluating NAND Formulas. The verifier incorrectly objected to the source’s bound c≤2Ac\le\sqrt{2}A after deriving the tighter estimate c≤A/2c\le A/\sqrt{2}, where A≥0A\ge0. Since the tighter estimate implies the stated bound, the objection confused tightness with correctness.

  • 57: Search via Quantum Walk. The assessed derivation used βi=18γ/(4π3i2)\beta_i=18\gamma/(4\pi^3i^2), consistent with the source’s error analysis, whereas one occurrence in the source’s complexity analysis prints π2\pi^2. The identity 43γ∑i=1∞βi=1/π\frac{4}{3\gamma}\sum_{i=1}^{\infty}\beta_i=1/\pi confirms that the π3\pi^3 choice is consistent with the stated error analysis. The verifier incorrectly treated this typographical inconsistency in the source as invalidating the assessed derivation.

In both examples, correcting the verifier’s assessment required no change to the submitted local derivation. Across all 23 corrected verifier judgments, the final complete-and-correct label remained unchanged for every affected output. Furthermore, on the negative instances, experts confirmed 100% of the sampled judgments.

Thank you for the detailed rebuttal and clarifications. While I appreciate the additional explanations, they do not significantly alter my overall assessment. Therefore, I will maintain my original score.

Reviewer_kX7POpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces the task of recovering the constants in TCS proofs. It introduces a benchmark, and a pipeline for LLMs to automatically do this, and some evaluation. however, the large part of the paper is presenting findings about the recovered constants.

Critical strengths
  • The paper addresses an interesting task that is of interest to TCS.

  • It introduces a benchmark and some evaluation results.

  • The proposed pipeline outperforms the baselines strongly.

Critical weaknesses
  • The paper is poorly written. It reads like a submission to a TCS conference repurposed for ICLR. In the introduction, it summarizes its contributions as if it is for a TCS venue:

"Our contributions. We use large language models (LLMs) to reconstruct the quantitative derivations left implicit in selected TCS proofs. We use the recovered derivations to measure coefficient sizes, explain how large factors arise, and identify estimates that can be tightened without changing the algorithm. We prepare self-contained benchmark documents with checked local and external premises and declared cost assumptions, including stipulated subroutine costs where needed. Models reconstruct the remaining internal calculations and compose explicit bounds under these assumptions."

I cannot easily tell from these sentences why these contributions are relevant to ICLR. They merely state that the authors uses LLMs to do something and how they did it. But using LLMs to accomplish some task is not necessarily a contribution to ICLR.

  • A large part of the paper (sec. 3) is about the findings about TCS papers. They are interesting, but not particularly relevant for ICLR.

  • For a contribution on new tasks and benchmarks relevant to ICLR, the motivation of the task/benchmark, how the benchmark is constructed, what it is trying to measure, the evaluation protocols need to be described in detail, in particular, which parts were done by humans. But the paper failed to do this. Only vague descriptions in Sec 2.1 are offered, and it is not clear how much human effort went into each step of the benchmark construction. If very little human effort was needed, then the benchmark may not be meaningful in the first place and the benchmark may just be measuring the gap between the evaluated models and the model that constructed the benchmark.

  • It is also not clear how the task itself relates to existing tasks in existing math benchmarks, and how it complements existing benchmarks, and what new capabilities it measures. The related work section is poorly written and does not provide clear answers.

  • It is not clear to what extent the proposed pipeline was used in benchmark construction. If this is the case, then the benchmark can be biased toward the proposed method.

  • The evaluation uses LLM as judge, but the audit reveals that it is not entirely reliable, and there's no details on the types of errors the judge makes.

  • The utility of the proposed pipeline seems only evaluated on Qwen and DeekSeek. Does it still help with frontier models? Results of one-shot frontier models do not seem to be provided, only those with the pipeline. so it is not clear what delta the pipeline provides on top of a frontier model.

Questions for authors

Please provide more details about how the benchmark is constructed.

5 comments

The paper is poorly written. It reads like a submission to a TCS conference repurposed for ICLR ...

A large part of the paper (sec. 3) is about the findings about TCS papers. They are interesting, but not particularly relevant for ICLR.

Thank you for the feedback. Our ICLR relevance lies in evaluating and improving LLM reasoning over quantitative arguments in research proofs through ConstEval, a reconstruction benchmark; ConstAble, a recovery pipeline; and a systematic study of hidden constants and their research implications.

1. Contributions and research utility

Recovering explicit bounds requires reconstructing proof dependencies, expanding omitted calculations, and composing local arguments with their applicability conditions. ConstAble organizes this inference through dependency-wise decomposition, local review and revision, and quantitative propagation (§2). ConstEval targets the important, underexplored recovery of hidden constants governing the practical significance of asymptotic bounds. Requiring explicit numerical bounds and supporting derivations, it tests whether models can reconstruct and justify quantitative guarantees, separately assessing bound completion, proof validity, and defect detection to support extended mathematical reasoning research and comparison of quantitative recovery methods.

In API experiments, ConstAble achieves 65.6%–92.5% completion versus at most 9.68% for expanded-generation and revision baselines at roughly comparable pooled median token use (Table 2), demonstrating this inference organization’s effectiveness for extended mathematical reasoning.

Sections 3 and 4 address complementary questions: Section 4 evaluates reconstruction performance and reliability, while Section 3 examines constants’ magnitudes, sources, and finite-size consequences, demonstrating the utility of inspectable derivations for mathematical analysis and AI-assisted discovery. Among 91 numerical targets, 69 representative coefficients are below 1,000 under the stated resource units and parameter settings. These derivations help TCS researchers and algorithm designers assess guarantees, locate proof losses, and sharpen analyses through:

  • Numerical amplification (§3.2): Intermediate bounds and dependencies reveal how parameters drive final resource costs through nested calls, repeated validation, and enumeration, including a squared sampling cost in the quantum-money proof.
  • Bound refinement (§3.3): Inspectable proof records support tighter guarantees in the three-distinctness analysis.
  • Finite-size guarantees (§3.4): Explicit coefficients enable concrete comparisons at finite input sizes; in the quantum-query example, retaining the coefficient shifts the intersection between the quantum upper and classical lower bounds from 16 to approximately 265.

2. Connections to established ICLR research

  • HARDMath: A Benchmark Dataset for Challenging Problems in Applied Mathematics (ICLR 2025) demonstrates the value of specialized mathematical evaluation through analytical approximation in applied mathematics; ConstEval instead reconstructs quantitative guarantees from extended research proofs.
  • The Ramanujan Library - Automated Discovery on the Hypergraph of Integer Relations (ICLR 2025) automates research on relations among mathematical constants, providing mathematical findings and a public resource; we similarly provide systematic knowledge and reusable derivations for constants in algorithmic bounds.
  • ShinkaEvolve: Towards Open-Ended and Sample-Efficient Program Evolution (ICLR 2026) combines LLM-based discovery with mathematical results, including improved circle-packing constructions, paralleling our combination of methodological advances and substantive mathematical findings.

Applications of Section 3 also connect to proof-content extraction (REFACTOR: Learning to Extract Theorems from Proofs, ICLR 2024) and LLM-driven scientific discovery (LLM-SR: Scientific Equation Discovery via Programming with Large Language Models, ICLR 2025), showing how recovered proof information supports further research.

For clarity, this work has not previously been submitted to a TCS conference.

Our methods, benchmark, and explicit derivations, identified in the submitted Introduction, support researchers in LLM reasoning, mathematical evaluation and verification, AI for mathematics, and TCS.

The utility of the proposed pipeline seems only evaluated on Qwen and DeekSeek. Does it still help with frontier models? Results of one-shot frontier models do not seem to be provided, only those with the pipeline. so it is not clear what delta the pipeline provides on top of a frontier model.

Thank you for raising this question. To directly quantify the pipeline’s benefit on a frontier model, we conducted an additional comparison using GPT-6.1 Sol with medium reasoning effort, evaluating both one-shot inference and our pipeline on the same set of 40 papers. Outputs from both workflows were reviewed using GPT-6.1 Sol with ultra reasoning effort.

WorkflowCompletion rate
Codex One-shot50.0% (20/40)
Codex Pipeline82.5% (33/40)

The pipeline improves the completion rate by 32.5 percentage points, yielding 13 additional complete-and-correct outputs across the 40 papers. This comparison directly measures the improvement over one-shot inference with the same underlying frontier model. The results show that the pipeline also provides a substantial benefit for GPT-6.1 Sol in this setting, extending the evidence beyond the Qwen and DeepSeek experiments.

For a contribution on new tasks and benchmarks relevant to ICLR, the motivation of the task/benchmark, how the benchmark is constructed, what it is trying to measure, the evaluation protocols need to be described in detail ...

Please provide more details about how the benchmark is constructed.

It is not clear to what extent the proposed pipeline was used in benchmark construction. If this is the case, then the benchmark can be biased toward the proposed method.

Thank you for raising these questions. We clarify the task and evaluation, the construction process and human responsibilities, and the relationship between benchmark construction and ConstAble below.

1. Motivation, task, and evaluation.

The submission explains the motivation in §1, defines the task in §2, describes benchmark construction in §2.1 and Appendices B.1–B.2, and specifies the evaluation protocol in §4.1 and Appendix D.1.

Hidden constants affect what asymptotic guarantees establish at concrete input sizes. Recovering explicit bounds from existing proofs can require reconstructing proof dependencies, expanding omitted calculations, and composing intermediate bounds while checking their hypotheses and resource costs. This motivates a quantitative reasoning task for LLMs: deriving an explicit guarantee through a sequence of valid, checkable proof steps. The task therefore examines whether a model can carry quantitative information through a proof and justify the resulting bound.

ConstEval evaluates this capability by requiring explicit bounds with supporting derivations, covering the specified resource model, parameter domain, guarantee mode, and requested clauses. Bound completion, proof validity, and injected-defect detection are evaluated separately; completion requires a correct, checkable derivation with all requested quantities explicit.

2. Benchmark construction and human responsibilities.

The construction procedure covers source selection, quantitative premises, human checks, instance validation, and paired defects. The 93 positive instances comprise 67 research-paper instances and 26 textbook expositions, each paired with a negative variant, giving 186 instances.

  • Research papers. Targets are main results of existing papers with complete proofs. LLMs assist with retrieving cited results, clarifying proofs, expanding omitted steps, and calculating external bounds. Human reviewers verify source versions, invoked statements, quantitative premises, numerical justifications, hypotheses, and resource costs. A separate checker reconstructs each retained target with the reference answer and construction reasoning withheld, checking parameter ranges, unresolved dependencies, and answer leakage.

  • Textbook expositions. The algorithms come from CP-Algorithms. GPT-5.6 Sol assists in drafting the expositions. Human reviewers select required external results or implementations and designate the main theorem’s complexity bound as the target. They check proof completeness, cost units, and recoverability, requiring revisions until these checks pass.

  • Negative variants. Each negative variant modifies one or two supporting proof blocks while preserving the target. Its defect annotations are fixed before evaluation.

Separately, TCS experts audit sampled proof-checking and defect-detection judgments.

3. Relationship to ConstAble and evaluation criteria.

The ConstAble pipeline was not used to construct either the research-paper instances or the textbook expositions in ConstEval. The LLM-assisted benchmark preparation described above follows a separate construction procedure. For the textbook component, §2.1 explicitly states: “Textbook construction uses its own prompts and runs separately from the ConstAble recovery workflow.” The worked examples distinguish supplied premises from quantities that solvers must recover. In the paired Table 1 comparisons, one-shot and pipeline runs receive the same prepared proof documents and target files within each model and execution mode, for both Qwen3.7 Plus and DeepSeek v4 Flash (§4.1; Appendix D.1).

Acceptance depends on establishing the requested quantitative guarantee under the specified assumptions, resource model, and parameter domain. Section 2 accepts alternative valid derivations within the supplied proof strategy and target specification, without requiring reproduction of the construction model’s reasoning trace. The resulting bound need not reproduce the construction model’s answer, except where a canonical expression or smallest integer constant is prescribed. Numerical tightness is otherwise assessed separately from completion.

4. Manuscript clarifications.

The revised §2.1 explicitly separates research-paper preparation from textbook construction and details the human responsibilities in each, bringing this account into the main text alongside the existing task definitions, premise checks, worked examples, and evaluation criteria.

Reviewer_RZNhOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces ConstEval, a benchmark for recovering explicit quantitative bounds from prepared theoretical-computer-science proofs, and ConstAble, a recovery pipeline guided by proof dependencies. ConstEval contains 93 positive instances and 93 paired documents with 147 injected atomic errors. ConstAble constructs a proof roadmap and dependency graph, extracts local arguments, and propagates explicit bounds and applicability conditions toward the target. It substantially improves judged bound completion over one-shot and expanded-inference baselines. The paper also uses recovered expressions to study coefficient magnitudes, finite-size guarantees, and opportunities to tighten proof estimates.

Critical strengths
  1. The benchmark defines a substantive quantitative reasoning task. Completion requires explicit bounds and supporting derivations for every requested clause and parameter regime, including the constants and conditions of invoked results (Section 2; Appendix B). ConstAble's intermediate records retain local derivations, source anchors, and applicability conditions for downstream composition. This makes the task and method useful for studying whether models can assemble complete quantitative arguments across proof dependencies.

  2. The completion advantage persists against substantial additional-generation baselines. Tables 1-2 compare the pipeline with one-shot inference, 13 independent generations, repeated review and revision, and sequential refinement. In the API settings, judged completion reaches 65.6% and 92.5%, while the expanded controls reach at most 9.68%. Parallel sampling receives credit whenever any of its 13 outputs completes the target, yet the gap remains large. Although budget matching is approximate, these results provide meaningful evidence that the structured workflow improves recovery under the evaluated protocols.

Critical weaknesses
  1. Validation of the final complete-and-correct labels needs clearer reporting. Separate GPT-6 Sol agent instances check proof validity and quantitative expansion (Section 4.1; Appendix D.1). Expert sampling and adjudication are valuable: the paper reports that 23 of 381 checking judgments were overturned, revised, and accepted by experts, while submitted answers remained fixed. However, the relationship between these judgments, the roughly one-fifth sample of evaluation data, and the short proof-fragment checks is not sufficiently clear. In particular, the manuscript does not establish the frequency of erroneous acceptance among outputs initially judged complete, separately by workflow. The 23 overturned judgments alone do not estimate that frequency, and separate instances of the same judging model may share systematic errors.

  2. Defect coverage does not establish the reliability of the full error reports. The reported coverage measures how many of the 147 injected annotations are correctly identified. The 10% expert audit of annotation-matching decisions supports the sampled FOUND judgments, but does not measure unsupported additional accusations or false alarms on the corresponding positive documents. A system can achieve high coverage while producing many incorrect defect claims, which would substantially increase the verification burden for researchers. This limitation is explicitly acknowledged in Section 5, but remains material to the claimed defect-detection capability.

Questions for authors
  1. What exactly are the units and sampling frame of the 381 audited judgments, and how are they distributed across models and workflows? A per-workflow breakdown of complete-and-correct, incomplete-but-valid, substantive-error, numerical-error-only, and no-proof outcomes would help interpret the completion and error rates together.

  2. Is an assessment available of the precision of all defect claims and the false-alarm rate on positive documents? A blinded sample, including claims outside the injected annotations, would already help clarify whether higher coverage produces reliable reports. Please distinguish this assessment from the existing audit of annotation-matching decisions.

2 comments

Thank you for your detailed review and for recognizing the value of expert sampling and adjudication in our evaluation. Your comments help us clarify how defect coverage, false alarms, and proof validation provide different kinds of evidence. Below, we address your concerns and specific questions in turn.

Defect coverage does not establish the reliability of the full error reports. The reported coverage measures how many of the 147 injected annotations are correctly identified. The 10% expert audit of annotation-matching decisions supports the sampled FOUND judgments, but does not measure unsupported additional accusations or false alarms on the corresponding positive documents. A system can achieve high coverage while producing many incorrect defect claims, which would substantially increase the verification burden for researchers. This limitation is explicitly acknowledged in Section 5, but remains material to the claimed defect-detection capability.

Is an assessment available of the precision of all defect claims and the false-alarm rate on positive documents? A blinded sample, including claims outside the injected annotations, would already help clarify whether higher coverage produces reliable reports. Please distinguish this assessment from the existing audit of annotation-matching decisions.

Thank you for highlighting the distinction between injected-defect coverage and the reliability of complete error reports. We agree that the existing 10% expert audit checks annotation-matching judgments: it assesses whether a reported finding correctly identifies a fixed injected defect. It does not estimate the precision of all defect claims, including additional accusations outside the injected annotations.

To assess unsupported defect accusations beyond the fixed injected annotations, we report an additional assessment of false alarms on the 93 negative instances in ConstEval. These were constructed from 26 textbook expositions and 67 research documents, with defects injected and checked as described in Section 2.1.

The unit of assessment is a document–configuration run. A false alarm is an unsupported accusation of a defect in the supplied proof. At most one false alarm was observed in any document–configuration run in this assessment. Human reviewers manually checked defect accusations on the negative documents and adjudicated which were unsupported. The results are:

Model / execution modeOne-shotPipeline, full workflow
GPT-5.6 Terra / Codex0/93 (0%)1/93 (1.08%)
GPT-5.6 Luna / Codex—0/93 (0%)
Qwen3.7 Plus / Codex0/93 (0%)3/93 (3.23%)
Qwen3.7 Plus / API1/93 (1.08%)1/93 (1.08%)
Qwen3.8 Flash / Codex—0/93 (0%)
Qwen3.8 27B / Codex—0/93 (0%)
DeepSeek v4 Flash 0731 / Codex0/93 (0%)1/93 (1.08%)
DeepSeek v4 Flash 0731 / API1/93 (1.08%)0/93 (0%)

Across the eight pipeline configurations, the observed document-level false-alarm rate ranges from 0% to 3.23%; seven configurations produce false alarms on at most one of the 93 negative documents. For the four paired Qwen3.7 Plus and DeepSeek configurations in Table 1, injected-defect coverage increases by 25.8–39.4 percentage points, while the pipeline produces false alarms on 0–3 negative documents per configuration. Thus, the higher coverage is accompanied by a low observed frequency of false alarms on these negative instances.

This assessment measures how often a run makes an unsupported defect accusation on a negative document. The existing 10% expert audit checks whether reported findings correctly match the fixed injected defects in the negative documents. Together, these assessments provide evidence on the correctness of sampled annotation matches and the frequency of false alarms on negative documents. The revised Section 4.2 reports these false-alarm results and clarifies the unit of assessment and the observation that each document–configuration run contained at most one false alarm.

Validation of the final complete-and-correct labels needs clearer reporting ...

What exactly are the units and sampling frame of the 381 audited judgments, and how are they distributed across models and workflows ...

Thank you for asking us to clarify the sampling units and the relationship between the expert audit and the final evaluation labels. We explain the sampling frame, audit units, and reported validation results below.

1. Audit sample.

The sampling frame contains 1,232 positive-instance outputs, each an answer to one positive instance under a specified model and execution configuration (Table 1; Appendices D.2–D.4):

Run typeConfigurationsFrame outputsAudited outputs
Codex pipelineSix configurations × 93; GPT-5.5: 37; Qwen3.8 Max: 11; Qwen3.8 Flash: 37643149
API pipelineDeepSeek v4 Flash and Qwen3.7 Plus: 93 each; Qwen3.8 27B: 3121750
One-shotQwen3.7 Plus and DeepSeek v4 Flash, each in Codex and API settings: 93 per configuration37275
Total1,232274

We randomly selected 274 outputs (22.2%, corresponding to “about 20%”). For each selected pipeline output, we randomly sampled one or two node-level proof fragments; for each selected one-shot output, we selected the complete proof. Experts reviewed 381 associated verifier judgments: 274 counts sampled outputs, whereas 381 counts judgments within them.

2. Verification and the 23 revisions.

Two GPT-6 Sol agents use fresh, separate sessions, also separate from source preparation, answer generation, and other-instance checks. They assess proof validity/premise support and quantitative completeness, respectively. Complete-and-correct requires explicit bounds with correct, checkable derivations covering every requested clause and parameter regime, including constants in invoked lemmas (Section 4.1; Appendix D.1).

Experts identified minor assessment issues in 23/381 judgments, mostly overly strict objections. For example:

  • [59] A Nearly Optimal Discrete Query Quantum Algorithm for Evaluating NAND Formulas. The verifier objected to the source’s bound c≤2Ac\le\sqrt{2}A after deriving c≤A/2c\le A/\sqrt{2}, where A≥0A\ge0, although the tighter estimate implies the stated bound.
  • [57] Search via Quantum Walk. The derivation used βi=18γ/(4π3i2)\beta_i=18\gamma/(4\pi^3i^2), consistent with the source’s error analysis and 43γ∑i=1∞βi=1/π\frac{4}{3\gamma}\sum_{i=1}^{\infty}\beta_i=1/\pi. The verifier incorrectly treated a source typo—π2\pi^2 in one occurrence in the complexity analysis—as invalidating this derivation.

GPT-5.5 Pro revised the 23 judgments in at most two rounds. Experts approved the revisions and reconfirmed each affected output’s original overall decision, with no change to its complete-and-correct status. All submitted answers remained fixed, including both local derivations above. On negative instances, experts confirmed 100% of sampled judgments.

3. Proof outcomes.

Appendix D.2, Table 8 reports all five categories—complete and correct, incomplete but valid, substantive error, numerical error only, and no proof delivered—for the six full-corpus Codex pipeline configurations, each covering 93 positive instances. In each of the six configurations, most outputs that do not achieve completion are valid but incomplete.

Appendix D.1 defines substantive errors as false or unsupported essential steps; numerical-only errors as correctable without changing the justified argument; and no proof delivered as an empty output or explicit proof deferral. Outputs with both substantive and numerical errors count as substantive.

Table 1 additionally reports substantive errors by model and execution mode on the same 67 research targets in each of four settings, totaling 268 outputs per workflow: 24/268 (9.0%) for one-shot, versus 9/268 (3.4%) for ConstAble. Completion is reported separately over all 93 positive targets.

4. Cross-model verification.

Appendix D.1 compares Claude Opus 5.5 xhigh and GPT-6.1 Sol ultra across 40 outputs (10 one-shot and 10 pipeline outputs each from Qwen3.7 Plus and DeepSeek v4 Flash). The two verifiers agree on 39 of 40 outputs (97.5%).

The sole disagreement involves the Qwen3.7 Plus pipeline output for the Dijkstra target, which requires an explicit bound valid for all n≥1n\ge1. The response derives a valid full-domain bound before simplifying it to 2496(m+nlg⁡n)2496(m+n\lg n) under n≥2n\ge2. Claude judges the output incorrect because the final expression omits the n=1n=1 case, whereas GPT judges it correct because the response provides the full-domain bound and explicitly states the simplification condition (detailed in Appendix D.1).

This comparison evaluates consistency across the two verifier model families on these sampled outputs. Since agreement alone does not establish correctness, the expert audit provides complementary evidence for the sampled judgments.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.