- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
STAB generates test cases for algorithm efficiency test. It writes programs to produce valid inputs that expose algorithmic runtime bottlenecks without a reference implementation. It decomposes the task into two modules. The constraint saturator extracts input constraints, builds a variable dependency graph saturates independent variables to their bounds, and resolves coupled groups with CP-SAT. The adversarial scenario injector matches the problem against a hand-curated catalog of 13 scenarios / 51 implementations via keyword matching, falling back to KNN over embedded anchor pools when no keyword matches, and returns worst-case construction principles. Both outputs plus the specification are encoded into a structured generation specification from which an LLM synthesizes a Python generator.
Validation is on 270 CodeContests problems across Python, Java and C++ with four LLMs, measured by Algorithmic Slowdown Rate (ASR): the fraction of generated tests whose runtime on an accepted solution exceeds that solution's maximum runtime over the CodeContests test set. STAB raises mean ASR from 53.94% to 72.65% over standard prompting, and reports 72.65% vs 35.37% (EvalPerf) and 37.35% (WEDGE), winning all 12 model–language cells.
Critical strengths
- The pipeline is intuitive and architecturally cheap, and still produces a large, consistent gain. The premise is that "Generating efficiency test cases is not equivalent to making inputs large. Worst-case behavior often depends on structure as well as size" and the architecture follows directly from it. There is no training, no execution feedback, no reference implementation, no iterative search and no per-model tuning and only utilizing this decomposition to keep the LLM's role narrow improves performance. It yields 50.43% → 73.45% (open-source) and 57.45% → 71.85% (closed-source) over standard prompting, and wins all 12 model–language cells against EvalPerf and WEDGE. It is easy to reimplement and easy to reason about when it fails.
- The ablation suite is thorough and reported at several levels of granularity. The authors do both module ablation and retrieval ablation, showing the effectiveness of the constraint saturator and the two components inside the adversarial scenario injector.
Critical weaknesses
-
M1 is the empirically stronger module, but its design is rigid in two ways, and I doubt it survives contact with anything that is not a Codeforces-formatted statement.
(a) Regex extraction has a narrow domain of applicability. The justification is frequency — "the same constraint patterns repeatedly appear across problem specifications" (p. 4) — which is true of CodeContests, the only corpus evaluated. The informative detail is the error decomposition: of the 9.3 points below M1's 90.66% accuracy, 8.2 are already the not-expressible-in-regex kind (prose-only 5.3%, unsupported notation 2.9%) and only 1.1 are parsing bugs. On the most formatting-regular corpus available the design is already at its ceiling, and Appendix J concedes that extension "requires a richer parser or an LLM-assisted constraint extraction step" (p. 18). Since specifications outside competitive programming rarely carry
1 ≤ N ≤ 100000notation, "specification-driven" in practice means "contest-formatted-specification-driven" — a considerably smaller claim than the title implies.(b) Maximization is hard-coded as the proxy for worst case, and bigger is not reliably slower. M1 assigns "the largest upper bound extracted for that variable", or via CP-SAT "a feasible assignment that makes the variables in the group large" (p. 4). Monotonicity of runtime in size is assumed everywhere and tested nowhere, and it fails in three ordinary cases: the objective is underdetermined (for
N·M ≤ 1000000, max-sum gives1000×1000, max-N gives1000000×1— different code paths entirely); aggregate bounds invert it (for the standard "sum of n over all test cases ≤ S" form, which the paper explicitly routes through CP-SAT as an "aggregate size constraint", saturation yields one maximal test, whereas the classic anti-test against solutions that re-initialize O(max N) state per test is T maximal with every n = 1); and threshold-branching solutions are slowest just below the branch, not at the bound. The paper's disclaimer that the boundary "is not a proof of the global maximum over the full input space" (p. 4) addresses a smaller concern — the maximizer of input size is simply not in general the maximizer of runtime. Because the pipeline is open-loop, nothing in it can detect the mismatch. The module works here because CodeContests problems are overwhelmingly monotone in n and uniformly formatted; in the settings where one would actually want this tool, both properties fail. -
M2 is a retrieval layer over a hand-authored knowledge base, so the method's structural coverage is bounded by what a human already knew to write down. The catalog is 13 scenarios and 51 implementations "compiled from standard algorithms and competitive programming references ... and foundational work on algorithmic complexity attacks" (p. 5); the keywords are hand-authored; and the KNN fallback is no more general, since its anchor pool is built by applying those same hand-written keywords to 5,306 CodeContests training problems (p. 13). Appendix J states the ceiling plainly: "Algorithm families not represented in the catalog have no corresponding construction principle to retrieve... Both gaps require manual extension of the catalog ... which the current pipeline does not automate" (p. 18).
Questions for authors
-
What is the CP-SAT objective function? The paper says only that the solver "returns a feasible assignment that makes the variables in the group large" (p. 4), which does not determine the output. Please state the objective and whether it varies by constraint type.
-
Is there any evidence about constraint formats outside CodeContests? Even a 30–50 problem pilot of M1 extraction accuracy on a corpus with less regular notation would substantially change how far I think the "specification-driven" claim reaches.
-
How does STAB relate to the symbolic-execution and performance-fuzzing literature (WISE, SlowFuzz, PerfFuzz, Singularity, Badger, PySE)? None is cited. Since Singularity searches over input patterns across scales — a structural objective — can you justify the abstract's claim that prior methods "do not address the structural input conditions that drive the algorithmic worst case" (p. 1)?
4 comments
Response to Reviewer qPDs [2/2]
Q2. Is there any evidence about constraint formats outside CodeContests? Even a 30–50 problem pilot of M1 extraction accuracy on a corpus with less regular notation would substantially change how far I think the "specification-driven" claim reaches.
Response to Q2
We additionally evaluate M1's constraint extraction on 50 Codeforces 2024-2025 problems. We normalize raw LaTeX notation into Unicode symbols to approximate rendered problem statements, without changing the constraints or M1's extraction mechanism. M1 achieves an extraction accuracy of 95.1%, supporting its applicability beyond CodeContests. We clarify that STAB's intended scope is competitive programming problems with explicit input constraints and time limits, rather than general software specifications.
Q3. How does STAB relate to the symbolic-execution and performance-fuzzing literature (WISE, SlowFuzz, PerfFuzz, Singularity, Badger, PySE)? None is cited. Since Singularity searches over input patterns across scales — a structural objective — can you justify the abstract's claim that prior methods "do not address the structural input conditions that drive the algorithmic worst case" (p. 1)?
Response to Q3
We thank the reviewer for pointing out related work on worst-case input generation through symbolic execution and performance fuzzing. These six studies are related to STAB because they also seek computationally expensive inputs, including structural worst-case patterns. We include them in Section 2 and revise the Abstract to narrow our prior-work claim. Our intended distinction is that STAB generates tests from problem specifications without accessing target implementations or runtime feedback.
These methods rely on a target implementation through program analysis or execution. This distinction matters because an algorithmic problem can have multiple accepted solutions with different runtime bottlenecks, and tests targeting one implementation do not necessarily expose bottlenecks in others. STAB instead combines input boundaries resolved from the problem specification with adversarial construction principles retrieved from its catalog. In Table 2, STAB improved bottleneck exposure across Fast, Slow, and Random solutions. In Table 4, STAB outperformed EvalPerf and WEDGE in all 12 model-language settings, even though these methods received reference implementations excluded from the evaluation solutions. These results support the effectiveness of specification-driven test generation across heterogeneous accepted solutions.
Revision Summary for Reviewer qPDs
We have uploaded the revised manuscript, with changes highlighted in blue. We clarify the scope of specification-driven generation (Abstract; Section 1), the coverage of regex-based constraint extraction, and the limitations of input-size maximization (Section 4.1). We specify the CP-SAT objective function (Appendix A), discuss the coverage limits of the hand-authored scenario catalog (Appendix K), and distinguish STAB from symbolic execution and performance fuzzing (Section 2). We welcome further discussion and are committed to addressing any remaining questions during the discussion period.
Thank you for your responses. My concerns are well addressed.
Response to Reviewer qPDs [1/2]
Response to W1
We thank the reviewer for discussing the limitations already acknowledged in Appendix K. We clarify that specification-driven refers to generating tests from algorithmic problem specifications without accessing target implementations, rather than supporting arbitrary software specifications. We clarify the competitive-programming scope in the revised Abstract and Section 1, and the limitations of input-size maximization in Section 4.1.
[Regex Extraction]
M1 targets explicit mathematical constraint notation commonly used in competitive programming. Appendix K already identifies irregular notation and prose-only constraints as limitations and discusses broader parser support as future work. Constraints not extracted by M1 remain in the full problem specification provided to the LLM for generator synthesis, although they are not incorporated into M1's boundary resolution. We clarify this constraint-format coverage in Section 4.1.
[Input-Size Maximization]
We agree that maximizing input size does not necessarily maximize runtime. M1 uses direct saturation or CP-SAT to determine large, constraint-satisfying input configurations, including alternative assignments for aggregate constraints. M2 then applies adversarial construction principles within these boundaries. Without execution feedback, STAB cannot identify every implementation-specific threshold or non-monotonic runtime pattern. Extending the search to such cases remains future work. We clarify in Section 4.1 that boundary maximization does not guarantee maximum runtime.
Response to W2
We thank the reviewer for discussing the catalog-coverage limitations already acknowledged in Appendix K. Extending the catalog to uncovered algorithm families and interaction-specific bottlenecks remains future work.
M2 is designed to reuse established adversarial construction principles across problems rather than require separate rules for every problem or algorithm combination. Its 13 scenarios and 51 representative implementations provide reusable construction principles. Keyword Match and the KNN fallback retrieve candidate scenarios, and the LLM adapts their construction principles to each problem specification and M1's admissible input boundaries. Problems combining multiple algorithms do not necessarily require their exact combinations to appear in the catalog when the relevant bottlenecks are captured by existing principles.
Response to Q1
We clarify the CP-SAT optimization objective and its constraint-dependent settings below. We also include these details in Appendix A of the revised manuscript.
For each dependent variable group G, CP-SAT maximizes the weighted sum ∑v∈Gwvxv subject to the extracted constraints. Independent variables are assigned their extracted upper bounds. The objective form remains fixed, but its weights vary for aggregate test-case constraints. By default, weights of 109, 106, and 1 are assigned to data-size variables in aggregate test-case constraints, other dependent variables, and the test-case count, respectively. For chained constraints such as k≤n≤105, the solver selects k=n=105. For product constraints such as n⋅m≤106, it favors extreme assignments such as (106,1) over (1000,1000) when no tighter bounds apply. For aggregate constraints, STAB additionally reverses the priorities between data size and test-case count, using weights of 1, 106, and 109, respectively. For example, when 1≤t≤104 and t test cases each contain n elements with tn≤2⋅105, the two settings yield (t=1,n=200,000) and (t=10,000,n=20).