# STAB: Specification-driven Testing for Algorithmic Bottlenecks

arXiv: https://arxiv.org/abs/2605.27981 · HTML: https://mlsanity.com/paper/2605.27981/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 21 of 21)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [An Empirical Evaluation of Using Large Language Models for Automated Unit Test Generation](https://mlsanity.com/paper/2302.06527/) (2023)
- [ReCode: Robustness Evaluation of Code Generation Models](https://mlsanity.com/paper/2212.10264/) (2022)
- [Code Generation with AlphaCodium: From Prompt Engineering to Flow Engineering](https://mlsanity.com/paper/2401.08500/) (2024)
- [ChatUniTest: A Framework for LLM-Based Test Generation](https://mlsanity.com/paper/2305.04764/) (2023)
- [Evaluating Language Models for Efficient Code Generation](https://mlsanity.com/paper/2408.06450/) (2024)
- [Code-Aware Prompting: A study of Coverage Guided Test Generation in Regression Setting using LLM](https://mlsanity.com/paper/2402.00097/) (2024)
- [EffiLearner: Enhancing Efficiency of Generated Code via Self-Optimization](https://mlsanity.com/paper/2405.15189/) (2024)
- [PerfCodeGen: Improving Performance of LLM Generated Code with Execution Feedback](https://mlsanity.com/paper/2412.03578/) (2024)
- [exLong: Generating Exceptional Behavior Tests with Large Language Models](https://mlsanity.com/paper/2405.14619/) (2024)
- [Synthesizing Performance Constraints for Evaluating and Improving Code Efficiency](https://mlsanity.com/paper/2505.23471/) (2025)
- [A Tool for Generating Exceptional Behavior Tests With Large Language Models](https://mlsanity.com/paper/2505.22818/) (2025)
- [ContractEval: A Benchmark for Evaluating Contract-Satisfying Assertions in Code Generation](https://mlsanity.com/paper/2510.12047/) (2025)
- [CodeContests-O: Powering LLMs via Feedback-Driven Iterative Test Case Generation](https://mlsanity.com/paper/2601.13682/) (2026)

## Abstract (arXiv)

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 test case generator. 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://github.com/suhanmen/STAB.