- 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
- 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.
- 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
- 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.
- 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
- How do the authors assess the reliability of LLM-based verification, particularly the possibility of systematic errors shared by generation and evaluation models?
- 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
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 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 after deriving the tighter estimate , where . Since the tighter estimate implies the stated bound, the objection confused tightness with correctness.
-
57: Search via Quantum Walk. The assessed derivation used , consistent with the source’s error analysis, whereas one occurrence in the source’s complexity analysis prints . The identity confirms that the 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.
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.
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≥1. The generated proof first derives a valid intermediate explicit bound holding for all n≥1, and then simplifies it into a final closed-form bound of 2496(m+nlgn) by invoking a threshold condition requiring n≥2. Claude marked the output Incorrect because the final reported expression omits the n=1 boundary case, whereas GPT marked it Correct because a valid bound covering all n≥1 was already explicitly established at an intermediate step and the final simplified coefficient is accurate under its stated n≥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.