STAB: Specification-driven Testing for Algorithmic Bottlenecks

High pass rates on established programming benchmarks such as HumanEval and LiveCodeBench do not always show whether a model can reason about algorithms. Many fixed benchmarks eventually become part of the public training ecosystem through released problem statements, editorials, and generated solutions, allowing later models to improve partly by exposure rather than by stronger algorithmic ability. We introduce ALGOBENCH, a framework that automatically builds novel algorithmic problems from known competitive-programming problems through structured constraint-shifting transformations. Each accepted ALGOBENCH variant is traceable to a source problem, but must make the original reference algorithm fail. Beyond pass@$k$, we introduce complexity-aware metrics -- including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS -- to test whether a solution is not only functionally correct but also asymptotically suitable for the generated problem. Experiments across multiple LLMs and prompting strategies show that performance drops sharply on ALGOBENCH variants, retrieval can increase reuse of the old algorithm, and many correct-looking solutions fail to meet the required complexity. Error analysis shows that failures are mainly algorithmic rather than implementation-level, suggesting that ALGOBENCH evaluates adaptation beyond functional correctness.

Large language models frequently generate code that appears correct on typical inputs yet fails on edge cases, invalid inputs, and other specification-defined corner conditions. A popular fix has the model write its own tests and repair until they pass, but the source of the gain is unclear: does it come from the tests merely existing, or from their grounding in a specification of what the code should do? We isolate this factor. Holding the tester, test budget, and repair loop fixed, we change a single prompt line that controls whether the tester receives the spec as a checklist of rules. The baseline is strong: it is already told to probe invalid inputs and edge cases. Grounding the tests in the spec produces correct code +38 percentage points more often than this baseline across three Claude tiers (Haiku 4.5, Sonnet 4.6, Opus 4.8), and +36 points on a held-out set. Grounding, not test quantity, is the primary driver: doubling the test budget barely helps, and combining eight independent ungrounded suites plateaus far below grounding. An ablation isolates the spec's content, not its format: given the spec as a plain paragraph the tester recovers 27 of 30 bugs, but asked to plan tests without the spec it recovers only 2 of 30. The effect survives stronger baselines: a property-based generator catches 28 of 30 bugs but invents out-of-spec requirements, and an AlphaCodium-style loop only matches the baseline. It replicates across vendors (GPT-5.3-codex +28, Gemini 3.5 Flash +19), with a task-level sign test over 18 tasks significant at p=0.002. Grounding improves both sensitivity and precision: it catches more real bugs and wrongly rejects far less correct code, cutting the false-alarm rate from 33% (68% against a Python standard-library oracle) to 0%. On well-specified algorithmic problems it neither helps nor hurts.

Test case synthesis is crucial for evaluating and ranking programs generated by large language models (LLMs). However, constructing high-quality test cases remains challenging because reliable expected outputs are often difficult to obtain. We propose Confidence-Gated Transductive Test Generation (CoTT), which first uses an efficient inductive procedure and invokes transductive generation only when inductive confidence is low. This adaptive design improves output reliability while allocating extra computation only when needed. On code reranking benchmarks, CoTT outperforms prior baselines across the reported metrics while reducing cost relative to applying transductive generation to every input. These results show that confidence-based allocation of test-time computation provides a favorable efficiency-effectiveness trade-off with a single efficient LLM.