acceptodds
Under review as a conference paper at ICLR 2027

STAB: Specification-driven Testing for Algorithmic Bottlenecks

Abstract

Evaluating the efficiency of algorithmic code requires test cases that expose runtime bottlenecks. Previous methods generate efficiency test cases either by increasing input size or by generating code-specific inputs that make the given implementation run slowly. Consequently, they do not address the structural input conditions that drive the algorithmic worst case. We introduce **STAB**, a specification-driven pipeline that generates test cases that expose algorithmic bottlenecks from a natural-language problem specification alone. STAB separates the task into constraint-bound maximization and adversarial structure injection. (i) The constraint saturator extracts constraints and resolves large admissible size assignments using rule-based saturation and CP-SAT optimization over related variables. (ii) The adversarial scenario injector retrieves implementation-level adversarial construction principles from a curated scenario catalog using keyword matching and K-nearest neighbors (KNN). STAB encodes the problem specification, resolved boundary, and retrieved construction principles into a structured generation specification, from which the LLM synthesizes a Python generator function. On CodeContests, STAB raises the rate of generated test cases that expose algorithmic bottlenecks from 50.43% to 73.45% on average across open-source LLMs and from 57.45% to 71.85% on average across closed-source LLMs, with consistent gains across Python, Java, and C++. Our code is available at https://anonymous.4open.science/r/Slow_TC-E2A8.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Efficiency Test-Case Generation, Algorithmic Bottleneck Exposure, Specification-Driven Generation, Large Language Models, Competitive Programming

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_qPDsOpenReview ↗
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
  1. 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.
  2. 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
  1. 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 ≤ 100000 notation, "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 gives 1000×1000, max-N gives 1000000×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.

  2. 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
  1. 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.

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

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

Response to Reviewer qPDs [1/2]

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

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.

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

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.

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

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 GG, CP-SAT maximizes the weighted sum ∑v∈Gwvxv\sum_{v\in G}w_vx_v 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 10910^9, 10610^6, and 11 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≤105k\leq n\leq10^5, the solver selects k=n=105k=n=10^5. For product constraints such as n⋅m≤106n\cdot m\leq10^6, it favors extreme assignments such as (106,1)(10^6,1) over (1000,1000)(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 11, 10610^6, and 10910^9, respectively. For example, when 1≤t≤1041\leq t\leq10^4 and tt test cases each contain nn elements with tn≤2⋅105tn\leq2\cdot10^5, the two settings yield (t=1,n=200,000)(t=1,n=200{,}000) and (t=10,000,n=20)(t=10{,}000,n=20).

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_RHg2OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper focuses on generating test cases that expose runtime bottlenecks in algorithmic code. The authors propose STAB, which focuses on the problem specification to generate test cases that can cover the natural language description. It consists of a constraint saturator and a CP-SAT solver to find the largest valid input sizes; a scenario injector that retrieves known worst-case constructions from a curated catalog of 13 scenarios using keyword matching or KNN; and an LLM to write a Python generator from these pieces. Experimental results on 270 CodeContests problems show that STAB raises the Algorithmic Slowdown Rate (ASR) from 53.94% to 72.65% on average across 4 LLMs and 3 languages, and it beats EvalPerf and WEDGE.

Critical strengths
  • Different from previous reference-based method EvalPerf and WEDGE, STAB only replies on problem specification. It seperates valid size boundary and input structure, and use the deterministic components such as a constraint saturator, a CP-SAT solver to provide reliable guidance for LLM-generated input generator.
  • STAB improves ASR for all 4LLMs and all 3 languages. It beats EvalPerf and WEDGE in all 12 models and outperforms HardTestGen and CodeContests-O.
Critical weaknesses
  • The ASR metric is weak and may not measure the effectiveness of generated tests. For example, a 0.1 ms difference in a 100ms solution will be counted as yes, but the difference may be due to runtime noise instead of a more difficult test. The paper does not report repeated runs or a noise threshold.
  • The paper doesn't test the real application of STAB: whether STAB can generate tests that can catch inefficient code. For example, how many incorrect timeout solutions in CodeContests can be caught by STAB tests before they submit? What is the precision and recall of these STAB test cases?
  • Simple LLM baselines are missing, such as prompts to use the maximum sizes to reason about the worst case first or let the LLM extract constraints instead of using regular expressions
  • Only one benchmark is used. The anchor pool and keywords come from the CodeContests training split. Results on other datasets would test generalization.
Questions for authors
  • Can you also report the median or mean ratio of new runtime to the CodeContests maximum for results in Table 2? Like the slowdown size in WEDGE and EvalPerf.
  • How does STAB perform when the retrieval of the scenario is wrong? In Table 9, only 72.59% of time it will get relevant scenarios, but KNN will always return 2 scenarios, even the similarity is low.
5 comments
AuthorsOpenReview ↗

Response to Reviewer RHg2 [1/3]

W1. The ASR metric is weak and may not measure the effectiveness of generated tests. For example, a 0.1 ms difference in a 100ms solution will be counted as yes, but the difference may be due to runtime noise instead of a more difficult test. The paper does not report repeated runs or a noise threshold.

Q1. Can you also report the median or mean ratio of new runtime to the CodeContests maximum for results in Table 2? Like the slowdown size in WEDGE and EvalPerf.

Response to W1 / Q1

We investigate whether ASR reflects more difficult tests rather than marginal runtime differences through six repeated runtime measurements, median slowdown ratios, and timing tolerances. The results show that STAB consistently produces larger slowdowns and outperforms Base across all four models. We report these analyses in Appendix N of the revised manuscript.

[Repeated Measurements and Median Slowdown Ratios]

Table W1-1 reports the mean and standard deviation across six repeated measurements. TC Median Slowdown is the median slowdown ratio across generated test cases, while Cell Median Slowdown is the median of maximum slowdown ratios within problem–language–solution cells. Both ratios use the maximum runtime from the CodeContests tests on the same solution as the reference. STAB achieves TC Median Slowdown of 2.18–2.58× and Cell Median Slowdown of 3.57–4.04×, exceeding Base across all four models. Its ASR standard deviations range from 0.85 to 1.05 percentage points, indicating limited variation across repeated measurements.

[Table W1-1. Repeated Measurements and Median Slowdown Ratios]

ModelMethodASR (%)TC Median SlowdownCell Median Slowdown
Qwen-3.5Base54.98±0.6654.98 \pm 0.661.49±0.031.49 \pm 0.032.50±0.072.50 \pm 0.07
STAB71.97±0.9271.97 \pm 0.922.18±0.092.18 \pm 0.093.57±0.273.57 \pm 0.27
Gemma-4Base48.05±0.6448.05 \pm 0.640.98±0.010.98 \pm 0.011.73±0.021.73 \pm 0.02
STAB77.25±1.0577.25 \pm 1.052.58±0.152.58 \pm 0.154.04±0.374.04 \pm 0.37
Gemini-3.1-FLBase46.09±1.4446.09 \pm 1.440.97±0.020.97 \pm 0.021.55±0.031.55 \pm 0.03
STAB74.07±0.8574.07 \pm 0.852.27±0.092.27 \pm 0.093.93±0.313.93 \pm 0.31
GPT-5.4-nanoBase64.42±0.6964.42 \pm 0.691.85±0.051.85 \pm 0.053.11±0.093.11 \pm 0.09
STAB71.51±1.0471.51 \pm 1.042.29±0.092.29 \pm 0.093.61±0.253.61 \pm 0.25

[Timing Tolerances]

Table W1-2 evaluates whether STAB generates more difficult tests by increasing the runtime threshold to kτ∗k\tau^{\ast}, where τ∗\tau^{\ast} is the maximum runtime induced by the CodeContests tests on the same solution. STAB outperforms Base across all eight thresholds and four models, demonstrating effective bottleneck exposure beyond marginal runtime increases.

[Table W1-2. ASR Across Timing Tolerances]

ModelMethodk=1k=1.1k=1.25k=1.5k=2k=3k=5k=10
Qwen-3.5Base54.98±0.6654.98 \pm 0.6652.68±0.4252.68 \pm 0.4250.38±0.5150.38 \pm 0.5147.07±0.3447.07 \pm 0.3440.88±0.3940.88 \pm 0.3933.35±0.4233.35 \pm 0.4225.29±0.5625.29 \pm 0.5616.65±0.4116.65 \pm 0.41
STAB71.97±0.9271.97 \pm 0.9268.59±0.7468.59 \pm 0.7465.41±0.7165.41 \pm 0.7160.89±0.9460.89 \pm 0.9452.00±1.5252.00 \pm 1.5241.44±2.0541.44 \pm 2.0531.09±2.2731.09 \pm 2.2719.74±1.6819.74 \pm 1.68
Gemma-4Base48.05±0.6448.05 \pm 0.6446.24±0.4546.24 \pm 0.4544.13±0.2944.13 \pm 0.2940.88±0.2940.88 \pm 0.2935.75±0.4635.75 \pm 0.4629.69±0.8729.69 \pm 0.8722.29±1.0022.29 \pm 1.0014.70±0.8414.70 \pm 0.84
STAB77.25±1.0577.25 \pm 1.0573.68±0.8173.68 \pm 0.8170.20±0.7970.20 \pm 0.7965.41±1.0665.41 \pm 1.0656.27±1.7556.27 \pm 1.7545.45±2.5145.45 \pm 2.5134.39±2.6834.39 \pm 2.6821.59±2.1421.59 \pm 2.14
Gemini-3.1-FLBase46.09±1.4446.09 \pm 1.4441.51±1.0041.51 \pm 1.0037.57±0.6637.57 \pm 0.6632.67±0.4232.67 \pm 0.4226.04±0.5926.04 \pm 0.5919.44±0.9619.44 \pm 0.9613.67±1.1813.67 \pm 1.187.87±0.857.87 \pm 0.85
STAB74.07±0.8574.07 \pm 0.8570.74±0.6670.74 \pm 0.6667.32±0.7167.32 \pm 0.7162.31±0.8162.31 \pm 0.8153.07±1.2953.07 \pm 1.2942.45±2.0142.45 \pm 2.0131.63±2.2731.63 \pm 2.2720.01±1.7820.01 \pm 1.78
GPT-5.4-nanoBase64.42±0.6964.42 \pm 0.6961.36±0.5461.36 \pm 0.5458.00±0.5058.00 \pm 0.5053.40±0.4853.40 \pm 0.4845.81±0.3945.81 \pm 0.3936.81±1.0136.81 \pm 1.0127.62±1.3727.62 \pm 1.3718.06±1.3818.06 \pm 1.38
STAB71.51±1.0471.51 \pm 1.0468.23±0.7968.23 \pm 0.7965.10±0.7365.10 \pm 0.7361.15±0.8761.15 \pm 0.8752.92±1.2852.92 \pm 1.2842.64±2.0542.64 \pm 2.0533.01±2.4533.01 \pm 2.4521.46±1.8421.46 \pm 1.84
AuthorsOpenReview ↗

Response to Reviewer RHg2 [2/3]

W2. The paper doesn't test the real application of STAB: whether STAB can generate tests that can catch inefficient code. For example, how many incorrect timeout solutions in CodeContests can be caught by STAB tests before they submit? What is the precision and recall of these STAB test cases?

Response to W2

STAB detects at least one timeout-incorrect solution in each of 17 CodeContests problems. However, its primary objective is to expose runtime bottlenecks in accepted solutions rather than classify timeout-incorrect solutions. Therefore, precision and recall for detecting timeout-incorrect submissions address a different evaluation objective.

As defined in Section 5.3, ASR measures whether generated tests induce runtimes exceeding the maximum observed on the CodeContests tests for the same solution, including cases that do not trigger TLE. Section 6.5 provides evidence of STAB's practical utility by examining runtime differences among accepted solutions. In Java, STAB increased the median runtimes of fast and slow solutions by 198% and 322%, respectively, compared with the CodeContests tests. The proportion of problems where the slow solution ran longer than the fast solution increased from 69.8% to 85.1%. In C++, the proportion of problems in the low-runtime regime, where runtime differences are difficult to observe, decreased from 54.4% to 15.9%. These results show that STAB makes runtime differences among accepted solutions more observable, supporting more informative code efficiency evaluation.

W3. Simple LLM baselines are missing, such as prompts to use the maximum sizes to reason about the worst case first or let the LLM extract constraints instead of using regular expressions

Response to W3

We additionally evaluate two LLM-based baselines following the reviewer's suggestions: Worst-Case Prompting and LLM Extraction. STAB outperforms both baselines across Gemini-3.1-FL and GPT-5.4-nano, demonstrating the effectiveness of explicit boundary resolution and adversarial scenario retrieval beyond LLM prompting alone.

Worst-Case Prompting uses a single LLM call to reason about maximum input sizes and worst-case structures, while LLM Extraction uses two calls for constraint extraction and test generation. The results below report the mean and standard deviation across six repeated runtime measurements on Python, Java, and C++. STAB achieves average ASRs of 74.07% and 71.51%, compared with 69.85% and 67.90% for Worst-Case Prompting and 69.61% and 69.71% for LLM Extraction on Gemini-3.1-FL and GPT-5.4-nano, respectively. STAB achieves the highest ASR in all six model-language settings.

ModelMethodPython (%)Java (%)C++ (%)Avg. (%)
Gemini-3.1-FLBase43.28±3.3643.28 \pm 3.3650.79±1.6850.79 \pm 1.6844.20±2.6944.20 \pm 2.6946.09±1.4446.09 \pm 1.44
Worst-Case Prompting67.11±1.1567.11 \pm 1.1573.37±0.7273.37 \pm 0.7269.07±2.9369.07 \pm 2.9369.85±1.4869.85 \pm 1.48
LLM Extraction66.78±0.6866.78 \pm 0.6873.58±0.1773.58 \pm 0.1768.47±2.4868.47 \pm 2.4869.61±1.0269.61 \pm 1.02
STAB73.18±0.4873.18 \pm 0.4876.56±0.5876.56 \pm 0.5872.48±2.3872.48 \pm 2.3874.07±0.8574.07 \pm 0.85
GPT-5.4-nanoBase61.48±1.3161.48 \pm 1.3167.87±0.9167.87 \pm 0.9163.90±1.6363.90 \pm 1.6364.42±0.6964.42 \pm 0.69
Worst-Case Prompting65.07±1.3365.07 \pm 1.3370.35±1.3170.35 \pm 1.3168.29±2.9168.29 \pm 2.9167.90±1.7567.90 \pm 1.75
LLM Extraction66.56±0.5766.56 \pm 0.5773.57±0.4373.57 \pm 0.4369.00±2.4469.00 \pm 2.4469.71±1.1369.71 \pm 1.13
STAB70.09±0.7970.09 \pm 0.7973.73±0.4673.73 \pm 0.4670.70±2.4370.70 \pm 2.4371.51±1.0471.51 \pm 1.04

W4. Only one benchmark is used. The anchor pool and keywords come from the CodeContests training split. Results on other datasets would test generalization.

Response to W4

We additionally evaluate STAB on the Codeforces 2024–2025 test dataset to assess its generalization beyond CodeContests. STAB outperforms Base across both models, demonstrating its effectiveness on an additional benchmark.

From Open-R1's 468-problem test set, we randomly select 200 problems with executable tests and at least three accepted C++ solutions. We generate five tests per problem using Gemini-3.1-FL and GPT-5.4-nano and evaluate Fast, Slow, and Random solutions. STAB achieves average ASRs of 74.37% and 74.83%, compared with 67.17% and 68.53% for Base, corresponding to relative improvements of 10.72% and 9.19%, respectively. STAB also achieves higher TC Median Slowdown on both models.

ModelMethodFast (%)Slow (%)Random (%)Avg. (%)TC Median Slowdown
Gemini-3.1-FLBase65.369.167.167.172.19
STAB72.376.574.374.373.51
GPT-5.4-nanoBase68.168.968.668.532.66
STAB73.875.974.874.833.34
AuthorsOpenReview ↗

Response to Reviewer RHg2 [3/3]

Q2. How does STAB perform when the retrieval of the scenario is wrong? In Table 9, only 72.59% of time it will get relevant scenarios, but KNN will always return 2 scenarios, even the similarity is low.

Response to Q2

We thank the reviewer for raising the concern about incorrect scenario retrieval. We examine 74 of the 270 problems (27.4%) where retrieved scenarios do not overlap with the annotated relevant scenarios, following the criterion in Appendix J, Table 10. In this subset, STAB achieves 0.10–3.50 percentage points higher average ASR than the variant without the adversarial scenario injector across all four models, indicating no observed decrease in average ASR relative to removing this module.

STAB prioritizes Keyword Match and invokes KNN top-2 without a similarity threshold only when no keywords match. Even when retrieved scenarios differ from the annotations, their adversarial construction principles can guide the LLM toward input ordering, structural properties, and value distributions that expose bottlenecks. Appendix F, Table 7 shows that conditional retrieval achieved 76.24% average ASR, compared with 68.98% without retrieval and 67.07% when the full catalog was provided.

Reviewer_7YnvOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

STAB generates efficiency tests from problem specifications by combining constraint-based boundary resolution, retrieval of adversarial construction principles, and LLM-based generator synthesis. The evaluation covers multiple models, programming languages, and accepted solutions.

Critical strengths
  1. The paper addresses a practical problem: generating informative performance tests without requiring the target implementation.
  2. Separating input scale from adversarial structure is intuitive and useful.
  3. The multi-model, multi-language evaluation and supplementary ablations provide useful empirical coverage.
Critical weaknesses
  1. Important related work is missing, leaving the incremental contribution unclear. AutoCode already includes structured worst-case and TLE-inducing test generation, together with explicit input validation. It is neither cited nor evaluated. Given STAB’s combination of standard constraint solving and catalog retrieval, a clear distinction and comparison with AutoCode’s relevant components are important.

  2. Input legality is insufficiently established. Running an accepted solution to obtain expected outputs and subsequently checking its execution does not independently verify that generated inputs satisfy all specification constraints. This leaves uncertainty about whether the reported slowdowns occur on valid inputs.

  3. ASR provides limited evidence of algorithmic bottleneck exposure. Any runtime increase over the original tests qualifies as success, regardless of magnitude. Slowdown distributions, repeated measurements, and meaningful timing tolerances are needed to distinguish substantial effects from marginal increases.

  4. Key methodological and comparison details are underspecified. The CP-SAT optimization objective for coupled variables is unclear, while baseline generation budgets and failure handling are insufficiently documented. These omissions limit reproducibility and interpretation of the reported improvements.

Questions for authors
  1. How does STAB differ from AutoCode’s structured worst-case and TLE-inducing test generation? Can the authors compare the relevant components under comparable budgets?

  2. Are generated inputs checked by an independent validator covering both numerical and structural constraints? Do the ASR improvements persist when restricted to independently validated inputs?

6 comments
AuthorsOpenReview ↗

Response to Reviewer 7Ynv [1/4]

W1. Important related work is missing, leaving the incremental contribution unclear. AutoCode already includes structured worst-case and TLE-inducing test generation, together with explicit input validation. It is neither cited nor evaluated. Given STAB’s combination of standard constraint solving and catalog retrieval, a clear distinction and comparison with AutoCode’s relevant components are important.

Q1. How does STAB differ from AutoCode’s structured worst-case and TLE-inducing test generation? Can the authors compare the relevant components under comparable budgets?

Response to W1 / Q1

We thank the reviewer for bringing AutoCode to our attention. We address this omission by including AutoCode in the related work and evaluating its test generation strategies under comparable budgets. While AutoCode relies on LLM prompting to construct validators and test generators, STAB explicitly resolves admissible input boundaries using constraint extraction and CP-SAT, and retrieves adversarial construction principles before LLM-based generator synthesis. We include the corresponding discussion and comparison in Section 2 and Appendix E of the revised manuscript.

[Methodological Differences]

AutoCode generates tests to distinguish correct and incorrect submissions and evaluates consistency with official verdicts using consistency, FPR, and FNR. Its three strategies comprise small-input enumeration (G1), random and extreme input generation (G2), and TLE-inducing worst-case construction (G3), with a validator filtering generated inputs. In contrast, STAB targets runtime bottlenecks in accepted solutions, including slowdowns that do not trigger TLE. Unlike AutoCode's G3, which prompts an LLM to construct TLE-inducing inputs and filters generated inputs through its Validator, STAB explicitly resolves admissible input boundaries using CP-SAT and retrieves adversarial construction principles before generator synthesis.

[Component-Level Comparison]

We reimplement AutoCode's Validator and evaluate G1, G2, and G3 separately on 100 CodeContests problems, using the same generation models, five intended test cases per problem, and five accepted solutions per language across Python, Java, and C++. STAB achieves higher average ASR than all three strategies. These results support the effectiveness of combining explicit boundary resolution with adversarial construction principles.

ModelMethodPython (%)Java (%)C++ (%)Avg. (%)TC Median Slowdown
Gemini-3.1-FLBase46.5549.0738.4044.671.00
AutoCode (G1)8.6224.3432.0821.680.98
AutoCode (G2)44.5255.4148.5649.501.06
AutoCode (G3)54.6062.5959.1658.781.94
STAB74.8675.7668.6473.092.16
GPT-5.4-nanoBase63.3866.9861.5263.961.97
AutoCode (G1)9.5122.9325.0019.151.00
AutoCode (G2)28.3135.0733.3632.251.85
AutoCode (G3)38.7044.3944.3242.472.13
STAB69.1472.8867.1669.732.15
AuthorsOpenReview ↗

Response to Reviewer 7Ynv [2/4]

W2. Input legality is insufficiently established. Running an accepted solution to obtain expected outputs and subsequently checking its execution does not independently verify that generated inputs satisfy all specification constraints. This leaves uncertainty about whether the reported slowdowns occur on valid inputs.

Q2. Are generated inputs checked by an independent validator covering both numerical and structural constraints? Do the ASR improvements persist when restricted to independently validated inputs?

Response to W2 / Q2

We thank the reviewer for distinguishing input legality from execution correctness. Since CodeContests does not provide independent validators covering all specification constraints, we construct additional numerical and structural constraint checks. The statistical analysis confirms that STAB's advantage over Base is significant both before and after validation, with the change in advantage remaining within an equivalence margin of ±3\pm 3 percentage points. We have added the validation details to Appendix M of the revised manuscript.

[Numerical and Structural Constraint Validation]

Using GPT-5.4-mini, we extract 1,485 explicit conditions from 270 problems and construct validators independently of accepted-solution outputs. We exclude 43 conditions from automated validation, including state-dependent conditions and interaction rules. Among the remaining 1,442 conditions across 13 categories, we retain 1,241 checks that do not incorrectly reject the existing CodeContests test cases. Table W2-1 summarizes these categories.

[Table W2-1. Constraint categories]

Validation ScopeConstraint Categories
13 categoriesRanges, product/sum/power bounds, sums across test cases, lengths, character sets, distinctness, permutations, value relations, parity/divisibility, primality, enumerated values, occurrence counts, graph structure

[Results on Independently Validated Inputs]

We define Validated ASR as successful bottleneck exposure only when generated inputs pass the retained independent checks. Table W2-2 shows that STAB outperforms Base across all four models by 4.46–27.78 percentage points (7.09–61.05% relative). Bootstrap tests confirm significant advantages both before validation (p≤0.002p \leq 0.002) and after validation (p≤0.007p \leq 0.007), with all 95% confidence intervals excluding zero. A TOST equivalence test further confirms that the change in the STAB–Base advantage remains within an equivalence margin of ±3\pm 3 percentage points. These results establish that STAB's advantage persists after independent numerical and structural constraint validation without a meaningful reduction.

[Table W2-2. ASR before and after additional validation]

ModelMethodASR (%)Validated ASR (%)
Qwen-3.5Base54.0251.26
STAB71.07 (+31.56%)66.81 (+30.34%)
Gemma-4Base46.8345.50
STAB75.82 (+61.90%)73.28 (+61.05%)
Gemini-3.1-FLBase48.8245.78
STAB72.87 (+49.26%)67.97 (+48.47%)
GPT-5.4-nanoBase66.0762.91
STAB70.83 (+7.20%)67.37 (+7.09%)

W3. ASR provides limited evidence of algorithmic bottleneck exposure. Any runtime increase over the original tests qualifies as success, regardless of magnitude. Slowdown distributions, repeated measurements, and meaningful timing tolerances are needed to distinguish substantial effects from marginal increases.

Response to W3

We thank the reviewer for highlighting the need to assess slowdown magnitude beyond ASR. We conduct six repeated runtime measurements and examine slowdown distributions and timing tolerances. The results consistently show that STAB outperforms Base across all four models. We report these analyses in Appendix N of the revised manuscript.

[Repeated Measurements and Slowdown Distributions]

Table W3-1 reports the mean and standard deviation across six measurements. We summarize slowdown distributions using TC Median Slowdown, computed across generated test cases, and Cell Median Slowdown, computed as the median of maximum slowdowns within problem–language–solution cells. STAB achieves TC Median Slowdown of 2.18–2.58× and Cell Median Slowdown of 3.57–4.04×, outperforming Base across all four models. Its ASR standard deviations range from 0.85 to 1.05 percentage points, indicating limited variation across repeated measurements.

AuthorsOpenReview ↗

Response to Reviewer 7Ynv [3/4]

[Table W3-1. Repeated Measurements and Slowdown Distributions]

ModelMethodASR (%)TC Median SlowdownCell Median Slowdown
Qwen-3.5Base54.98±0.6654.98 \pm 0.661.49±0.031.49 \pm 0.032.50±0.072.50 \pm 0.07
STAB71.97±0.9271.97 \pm 0.922.18±0.092.18 \pm 0.093.57±0.273.57 \pm 0.27
Gemma-4Base48.05±0.6448.05 \pm 0.640.98±0.010.98 \pm 0.011.73±0.021.73 \pm 0.02
STAB77.25±1.0577.25 \pm 1.052.58±0.152.58 \pm 0.154.04±0.374.04 \pm 0.37
Gemini-3.1-FLBase46.09±1.4446.09 \pm 1.440.97±0.020.97 \pm 0.021.55±0.031.55 \pm 0.03
STAB74.07±0.8574.07 \pm 0.852.27±0.092.27 \pm 0.093.93±0.313.93 \pm 0.31
GPT-5.4-nanoBase64.42±0.6964.42 \pm 0.691.85±0.051.85 \pm 0.053.11±0.093.11 \pm 0.09
STAB71.51±1.0471.51 \pm 1.042.29±0.092.29 \pm 0.093.61±0.253.61 \pm 0.25

[Timing Tolerances Across Repeated Measurements]

Table W3-2 evaluates ASR under eight runtime thresholds defined by kτ∗k\tau^{\ast}, where τ∗\tau^{\ast} is the maximum runtime induced by the CodeContests tests on the same solution. STAB outperforms Base at every threshold across all four models, demonstrating that its advantage extends beyond marginal runtime increases.

[Table W3-2. ASR Under Timing Tolerances]

ModelMethodk=1k=1.1k=1.25k=1.5k=2k=3k=5k=10
Qwen-3.5Base54.98±0.6654.98 \pm 0.6652.68±0.4252.68 \pm 0.4250.38±0.5150.38 \pm 0.5147.07±0.3447.07 \pm 0.3440.88±0.3940.88 \pm 0.3933.35±0.4233.35 \pm 0.4225.29±0.5625.29 \pm 0.5616.65±0.4116.65 \pm 0.41
STAB71.97±0.9271.97 \pm 0.9268.59±0.7468.59 \pm 0.7465.41±0.7165.41 \pm 0.7160.89±0.9460.89 \pm 0.9452.00±1.5252.00 \pm 1.5241.44±2.0541.44 \pm 2.0531.09±2.2731.09 \pm 2.2719.74±1.6819.74 \pm 1.68
Gemma-4Base48.05±0.6448.05 \pm 0.6446.24±0.4546.24 \pm 0.4544.13±0.2944.13 \pm 0.2940.88±0.2940.88 \pm 0.2935.75±0.4635.75 \pm 0.4629.69±0.8729.69 \pm 0.8722.29±1.0022.29 \pm 1.0014.70±0.8414.70 \pm 0.84
STAB77.25±1.0577.25 \pm 1.0573.68±0.8173.68 \pm 0.8170.20±0.7970.20 \pm 0.7965.41±1.0665.41 \pm 1.0656.27±1.7556.27 \pm 1.7545.45±2.5145.45 \pm 2.5134.39±2.6834.39 \pm 2.6821.59±2.1421.59 \pm 2.14
Gemini-3.1-FLBase46.09±1.4446.09 \pm 1.4441.51±1.0041.51 \pm 1.0037.57±0.6637.57 \pm 0.6632.67±0.4232.67 \pm 0.4226.04±0.5926.04 \pm 0.5919.44±0.9619.44 \pm 0.9613.67±1.1813.67 \pm 1.187.87±0.857.87 \pm 0.85
STAB74.07±0.8574.07 \pm 0.8570.74±0.6670.74 \pm 0.6667.32±0.7167.32 \pm 0.7162.31±0.8162.31 \pm 0.8153.07±1.2953.07 \pm 1.2942.45±2.0142.45 \pm 2.0131.63±2.2731.63 \pm 2.2720.01±1.7820.01 \pm 1.78
GPT-5.4-nanoBase64.42±0.6964.42 \pm 0.6961.36±0.5461.36 \pm 0.5458.00±0.5058.00 \pm 0.5053.40±0.4853.40 \pm 0.4845.81±0.3945.81 \pm 0.3936.81±1.0136.81 \pm 1.0127.62±1.3727.62 \pm 1.3718.06±1.3818.06 \pm 1.38
STAB71.51±1.0471.51 \pm 1.0468.23±0.7968.23 \pm 0.7965.10±0.7365.10 \pm 0.7361.15±0.8761.15 \pm 0.8752.92±1.2852.92 \pm 1.2842.64±2.0542.64 \pm 2.0533.01±2.4533.01 \pm 2.4521.46±1.8421.46 \pm 1.84

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.