{"id":"c138d125-6237-4441-a316-b5e4df02e619","arxiv_id":"2507.13337","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Frontier reasoning models solve fewer than 1 percent of FormulaOne, a new benchmark of MSO-logic dynamic programming problems on tree-like graphs.","lead":"FormulaOne is a new benchmark of 120 hard graph-algorithm problems generated via Monadic Second-Order logic, and frontier AI models (o3, Gemini 2.5 Pro, Grok 4) solve under 1 percent of them even with sample attempts and few-shot examples. The paper argues this exposes a gap between current model performance and the deep multi-step reasoning needed for real-world optimisation tasks, and offers a scalable source of verifiable problems for training and evaluation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing human baseline makes the <1% model failure uninterpretable as a measure of algorithmic reasoning depth; Section 2.1 asserts expert human competence without evidence.","rationale":"The reader's weakest_assumption identifies two attached premises: the fairness of the evaluation interface and the absence of a human baseline. I agree that the missing human baseline is the more load-bearing of the two, because it is the premise that converts a raw failure rate into a statement about 'expert-level algorithmic reasoning'. The interface concern is real but can be partially absorbed by the human baseline: if human experts succeed on the same interface, then the interface is not the primary barrier; if they fail, the interface becomes a plausible confound. The reader already conditions her verdict on these premises, so my stress-test does not move the verdict; it sharpens the reason for conditionality. I chose 'partial' rather than 'agree' because the reader lists the interface and human baseline as a single bundle, whereas I would elevate the human baseline as the decisive, independently testable assumption. Secondary concerns (SETH-optimality claims, withheld data/code) are noted in the manuscript but do not undermine the central failure-rate claim as directly; they affect the paper's broader theoretical framing and reproducibility, not the core interpretation of the <1% result.","tokens_in":16620,"tokens_out":3564,"duration_ms":46595,"concrete_test":"Recruit 5-10 participants with strong algorithmic backgrounds (e.g., competitive programmers rated >=2400 or PhD students specializing in treewidth algorithms). Give each a random sample of 20 FormulaOne problems using the exact same evaluation interface described in Section 4.1: implement the five callbacks, graph restricted to the current bag, no visibility of the full graph during updates, and no feedback on test failures. Use the same problem statements, test suites, and time limits (with a reasonable extension, e.g., 2 hours per problem, to reflect human working style). Measure the median fraction of problems solved. If the median is not substantially above the model rate (e.g., below 20%), then the benchmark does not establish a model-human capability gap and the central claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central interpretive claim is that frontier models remain 'far from expert-level understanding' (Abstract) and that a 'human expert of that calibre should, by rights, be able to score highly on our problems' (Section 2.1). This is an empirical premise, but no human baseline is reported anywhere in the manuscript. Without such a baseline, the <1% success rate of o3, Gemini 2.5 Pro, and Grok 4 Heavy is uninterpretable as a measure of algorithmic reasoning depth: the low scores could equally stem from (a) the nonstandard callback-interface, which hides the full graph during DP updates and forbids iterative debugging; (b) ambiguities or errors in the generated problem descriptions or verifiers; or (c) the possibility that the benchmark's tasks are not actually solvable by humans at the claimed rate within the given constraints. The one fully worked solution in Appendix A demonstrates that at least one problem is humanly solvable, but it does not calibrate the difficulty of the other 119 problems. The paper itself confirms the importance of this assumption: the entire narrative of 'depth of algorithmic reasoning' depends on humans scoring substantially above 1%, yet this is never tested. The SETH-optimality claims and the absence of released data/code are secondary: even if both were fixed, the missing human baseline would still leave the core capability-gap conclusion unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces FormulaOne, a benchmark of 120 problems composed of dynamic programming over graphs of treewidth at most 3, generated from Monadic Second-Order (MSO) logic formulas. Each problem asks the model to compute a weighted model count modulo 1e9+7, given the graph, a tree decomposition, and vertex weights. To focus the task, the authors provide an evaluation environment with five callback functions (leaf, introduce, forget, join, extract), which hides the full graph during DP updates. They evaluate o3, o3-Pro, Gemini 2.5 Pro, and Grok 4 Heavy and report success rates below 1% (0 or 1 of 120), plus a 100-problem warmup set with substantially higher success rates. The paper argues that this demonstrates that frontier models lack the deep algorithmic reasoning needed for real-world research problems and claims connections to SETH-based lower bounds. The authors state they release the full corpus and evaluation framework.","tokens_in":16869,"tokens_out":6317,"duration_ms":76702,"significance":"If the results are properly calibrated, FormulaOne would be a valuable benchmark: it is generated from MSO logic with automated verifiers, it is in-distribution for language models in the sense of being an algorithmic coding task, and it offers a potentially unbounded stream of verifiable hard problems for reinforcement learning with verifiable rewards. The paper's strengths include a carefully described evaluation environment, a thoughtful analysis of common DP failure modes, a detailed worked solution for one problem in Appendix A, and a warmup dataset that spans a difficulty gradient. However, the central interpretation rests on two unverified premises: that expert humans would score far above 1% on the same interface, and that the self-generated DSL verifiers are correct. Both are load-bearing for the claim that the benchmark measures the depth of algorithmic reasoning rather than interface unfamiliarity. Until these are addressed, the benchmark's significance as a measure of reasoning depth remains conditional.","major_comments":[{"comment":"The headline claim that frontier models are 'far from expert-level understanding' depends on the premise, stated in Section 2.1, that a human expert of Codeforces-calibre should 'by rights' score highly on these problems. No human baseline is reported anywhere in the manuscript. The one fully worked solution in Appendix A shows that at least one problem is humanly solvable, but it does not calibrate the other 119 problems. Since the evaluation interface requires implementing five callbacks that operate only on the current bag of the tree decomposition, hides the full graph during DP updates, and does not allow iterative debugging, the <1% success rate could reflect interface unfamiliarity rather than reasoning depth. The authors should add a human baseline using the same interface and time limits, or substantially weaken the expert-level interpretation.","section":"Section 2.1 and Section 5.2"},{"comment":"The ground truth for the benchmark is generated by the authors' own DSL and verifiers, with no described independent verification. The paper states that the verifier maps any input to the correct answer, but the correctness of those verifiers is itself asserted by the same pipeline. I found no independent brute-force cross-checks, no differential testing against known algorithms, and no manual verification of a random sample. The abstract and introduction say the corpus and evaluation framework are released, but no URL, repository, or artifact is provided in the manuscript. Without code and data, the reported success rates cannot be audited or reproduced. Please release the artifacts and add independent validation (e.g., brute-force checks on small graphs with an independently written verifier, or a manual verification protocol).","section":"Section 4.2 and Section 2.2"},{"comment":"The paper claims that 'the best-known time complexity of a large portion of our dataset is, in fact, optimal under SETH' and that algorithmic progress on these problems could refute a central conjecture in theoretical computer science. I could not find a concrete identification of which problems in the dataset have this property, nor citations of the specific lower bounds. This is a strong theoretical claim that goes beyond the benchmark's empirical findings and, as written, overstates the significance. The authors should either specify the dataset problems and cite the relevant SETH lower-bound results, or replace the claim with a more modest statement about conceptual proximity to fine-grained complexity results.","section":"Section 2.1 and Section 3"},{"comment":"The model comparison is not apples-to-apples: o3 and Gemini 2.5 Pro are scored with 10 attempts (@10), while o3-Pro and Grok 4 Heavy are scored with one attempt (@1), and Grok was additionally given internet access. With 120 problems, the difference between 0 and 1 solved problems is not statistically meaningful, yet the text describes Grok as 'solving none' in a way that implies a ranking. Please report per-attempt success rates, confidence intervals, and use matched evaluation budgets when comparing models.","section":"Section 5.2 and Table/Figure 8"}],"minor_comments":[{"comment":"The prompt is said to 'be found in full here' and the dominating-set solution is said to be 'written in Python, here', but no links or appendix content are present in the manuscript. Please include the actual artifacts or remove the pointers.","section":"Section 5.1 and Section 3.2"},{"comment":"The appendix is titled 'Algorithm for Maximal Cluster Graph' and is described as a full solution, but it contains no runnable code and no formal proof of correctness for the DP transitions, such as the obligation-bit merge rule at join nodes. Consider adding a complete implementation and a correctness argument.","section":"Appendix A"},{"comment":"The category-level success rates are computed over the combined FormulaOne and FormulaOne-Warmup datasets, but some categories have very small sample sizes (e.g., EPSILON with 4 problems and MODULAR with 10); the displayed rates are therefore noisy and should be interpreted with caution.","section":"Figure 10"},{"comment":"The claim that the sampling process ensures that 'with high probability' all possible gadgets are present in the tested graphs is not quantified. Please state what 'all possible gadgets' means and give the probability or a formal argument.","section":"Section 4.3"},{"comment":"The abstract says 'We release the full corpus along with a comprehensive evaluation framework', while the introduction says 'we will release the full dataset'; please make the release status consistent and, if released, provide a permanent link.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"This is a promising benchmark with a carefully designed evaluation environment, but the missing human baseline and the lack of released artifacts are serious calibration gaps. I would be willing to reconsider after the authors add a human evaluation and make the verifiers/data/code available for independent audit. The SETH-related claims should also be substantiated or toned down. The paper is a reasonable fit for the journal's scope if these issues are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know about this paper is that the headline result is real: on a new benchmark of 120 weighted model-counting problems over low-treewidth graphs, generated semi-automatically from MSO formulas, o3, Gemini 2.5 Pro, and Grok 4 Heavy solve essentially nothing—one problem each at most, under 1%. The generation pipeline is genuinely new: a DSL takes MSO formulas and emits a human-readable problem statement, a verifier, and test suites. That gives an unbounded family of automatically verifiable DP problems, which is exactly what RLVR environments need. The accompanying 100-problem warmup set is a smart addition: it shows models do much better on simpler problems from the same distribution, which is decent evidence that the interface itself isn't the sole obstacle.\n\nThe evaluation is careful. Models only implement five callbacks on a provided tree decomposition; the test suites include consistency across decompositions, brute-force correctness checks on small graphs, and efficiency tests to catch non-linear implementations. The failure-mode analysis is concrete and useful.\n\nThe main soft spot is the missing human baseline. The paper asserts that a human expert of competitive-programming calibre 'should, by rights' score highly. That is an empirical premise, and it is never tested. Without it, the <1% tells us models fail on these tasks, but it doesn't calibrate the distance to expert humans. The fully worked solution in Appendix A shows one problem is humanly solvable, not that all 120 are reasonably solvable under the same constraints. I'd argue the warmup results partly mitigate the 'interface artifact' worry, but the expert-comparison claim remains under-supported. Add a small human study, even on a subset, and this becomes much stronger.\n\nTwo minor points. The SETH connection is mentioned often but never pinned to specific problems or lower-bound results; it's motivation, not evidence, and should be framed as such. The data and code are promised but absent from the preprint; for a benchmark paper that's a review blocker in practice. Also, calling the tasks 'in-distribution' is slightly generous: the callback-on-tree-decomposition format is probably unfamiliar to models, even if the graph theory isn't.\n\nThis paper deserves a serious referee. The generation method and the empirical result are solid contributions. I'd bring it to reading group and would cite the benchmark in my own work. Recommend: peer review, conditional on a human baseline and released artifacts.","headline":"A genuinely new, verifiable benchmark with a credible <1% model failure rate; the missing human baseline tempers the 'expert-level reasoning' interpretation but doesn't sink the main result.","tokens_in":17455,"tokens_out":3671,"would_cite":true,"duration_ms":42561,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"FormulaOne, a benchmark built from Monadic Second-Order logic on graphs, shows frontier reasoning models solve under 1 percent of its hard algorithmic problems, indicating a reasoning-depth gap that competitive-programming scores do not…","keywords":["MSO logic on graphs","tree decompositions","dynamic programming","algorithmic reasoning benchmark","weighted model counting","frontier AI evaluation","treewidth","RLVR environment"],"falsifier":"Run the same 120 problems with a debugging loop in which the model can execute its code on sample tests and revise its five callback implementations before final scoring; if success rises substantially, the under-one-percent result is an artifact of one-shot code generation rather than a reasoning limit. Alternatively, administer the identical benchmark to a panel of top human competitive programmers; if they also solve near 1 percent, the human-expert comparison collapses.","tokens_in":16429,"feed_emoji":"🧩","tokens_out":7683,"duration_ms":87925,"temperature":0.7,"pith_summary":"This paper introduces FormulaOne, a benchmark of 120 graph-algorithm problems designed to measure the depth of algorithmic reasoning rather than breadth of knowledge. The problems are all instances of weighted model counting for properties expressible in Monadic Second-Order (MSO) logic on graphs with small treewidth, and each is guaranteed by an algorithmic meta-theorem to have an efficient dynamic-programming solution. The authors report that frontier reasoning models, given substantial scaffolding and multiple sampled completions, solve fewer than one percent of these problems, while a curated easier companion set, FormulaOne-Warmup, is handled substantially better. The intended conclusion is that current models can imitate competitive programming but cannot yet perform the long, interdependent chains of reasoning that real research problems require.","feed_headline":"Frontier models solve under 1% of a new logic-built benchmark","feed_subtitle":"The 120-task FormulaOne set demands deep multi-step reasoning; even top reasoning models rarely finish one task.","key_machinery":"The carrying object is the pairing of MSO logic with tree-decomposition dynamic programming. MSO logic is a formal language for graph properties in which one may quantify over vertices, edges, and sets of them; an algorithmic meta-theorem guarantees that any MSO-definable problem can be solved in time linear in the graph order once a bounded-width tree decomposition is supplied. The paper's domain-specific language converts MSO formulas into human-readable problem statements, verifying programs, test suites, and state-complexity estimates, and the evaluation interface asks models to supply only the five dynamic-programming transition callbacks. This machinery makes the benchmark simultaneously hard, automatically verifiable, scalable, and in-distribution, which is why the near-total model failure is taken as evidence about reasoning depth rather than about unfamiliar formats.","core_discovery":"The central claim is that a benchmark generated from MSO logic on graphs can separate frontier models' competitive-programming competence from expert-level algorithmic reasoning, and that under this separation current models fall far short. Each FormulaOne problem presents a graph, a tree decomposition, and vertex weights, and asks for the sum of weights of all subsets satisfying an MSO-definable constraint, modulo $10^{9}$+7. Because constraints are MSO-definable, every problem is solvable by a fixed-parameter linear dynamic program running over the supplied tree decomposition; the evaluation harness reduces the model's task to implementing five callbacks for leaf, introduce, forget, join, and root extraction. The paper reports that frontier reasoning models solve at most one of the 120 hard problems even with multiple attempts, and argues this failure is fundamental rather than a prompt-engineering artifact. The dataset also connects several of its hardest problems to the Strong Exponential Time Hypothesis, so genuinely better algorithms discovered on it would have theoretical consequences.","pith_inferences":["An obvious test the paper does not run is to let models debug against failing test cases: the reported result is for multiple independent completions with no feedback loop, so part of the gap may reflect inability to find and fix implementation bugs rather than inability to design the dynamic program.","The human-expert baseline is asserted, not measured; a controlled study giving top human competitive programmers the same five-callback interface would sharpen the claim that the benchmark tracks reasoning depth.","The connection between reasoning depth and model failure could be tested directly by generating formulas with graded numbers of interdependent state features and checking whether model success decays smoothly with that measure.","Extending the framework to optimisation objectives, different graph parameters, or requiring models to produce the tree decomposition themselves would likely lower success further, but would also change what the benchmark isolates."],"forward_implications":["If the under-one-percent result holds, current competitive-programming benchmark scores overstate how close frontier models are to expert algorithmic reasoning, because FormulaOne is deliberately in-distribution.","The MSO-based generation framework can produce a virtually unlimited stream of new problems with guaranteed correct answers, making FormulaOne a candidate training environment for reinforcement learning with verifiable rewards.","A model that solves a substantial share of FormulaOne would demonstrate a capability current systems lack, and one that improves on the known algorithm for a SETH-linked problem would carry consequences for complexity theory.","FormulaOne-Warmup provides a graded ladder of same-distribution problems, allowing incremental measurement of progress before models can attack the hard set."],"supporting_citations":[{"why":"Supplies the meta-theorem that every MSO-definable property is solvable by linear-time dynamic programming on bounded-treewidth graphs, the theoretical foundation of the generated problems.","marker":"[Cou90]"},{"why":"Documents the competitive-programming success of frontier reasoning models that the paper contrasts with its near-zero FormulaOne scores.","marker":"[EWS+25]"},{"why":"Gives lower bounds showing many bounded-treewidth algorithms are optimal under the Strong Exponential Time Hypothesis, tying dataset difficulty to complexity theory.","marker":"[LMS11]"},{"why":"Exemplifies the research-frontier problems, treewidth-parameterized enumeration, that several FormulaOne problems are drawn from.","marker":"[KM24]"},{"why":"Foundational dynamic programming on bounded-treewidth graphs, the traversal technique the evaluation harness automates.","marker":"[Bod88]"}],"fun_headline_variants":["Frontier AI fails 99% of a new logic benchmark","Reasoning beyond code: benchmark exposes AI limits","New benchmark: AI solves under 1% of tasks","MSO-logic benchmark stumps top AI models","Graph reasoning test: top models score below 1%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the callback-based interface is a fair test of reasoning depth and that expert human programmers would score far above 1 percent on it; if either premise fails, the low success rate would not establish a reasoning-depth gap.","fun_headline_variants_meta":{"raw":{"variants":["Frontier AI fails 99% of a new logic benchmark","Reasoning beyond code: benchmark exposes AI limits","New benchmark: AI solves under 1% of tasks","MSO-logic benchmark stumps top AI models","Graph reasoning test: top models score below 1%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1559,"prompt_tokens":1055,"completion_tokens":504,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":426}},"tokens_in":671,"tokens_out":504,"duration_ms":6723,"temperature":1.0,"reasoning_tokens":426,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:25:16.519811+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same 120 problems with a debugging loop in which the model can execute its code on sample tests and revise its five callback implementations before final scoring; if success rises substantially, the under-one-percent result is an artifact of one-shot code generation rather than a reasoning limit. Alternatively, administer the identical benchmark to a panel of top human competitive programmers; if they also solve near 1 percent, the human-expert comparison collapses.","supporting_citations":[],"review_version":1}