The emergence of large language models (LLMs) has significantly pushed the
frontiers of program synthesis. Advancement of LLM-based program synthesis
calls for a thorough evaluation of LLM-generated code. Most evaluation
frameworks focus on the (functional) correctness of generated code; efficiency,
as an important measure of code quality, has been overlooked in existing
evaluations. In this work, we develop ENAMEL (EfficeNcy AutoMatic EvaLuator), a
rigorous and high-standard benchmark for evaluating the capability of LLMs in
generating efficient code. Firstly, we propose a new efficiency metric called
eff@k, which generalizes the pass@k metric from correctness to efficiency and
appropriately handles right-censored execution time. Furthermore, we derive an
unbiased and variance-reduced estimator of eff@k via Rao--Blackwellization; we
also provide a numerically stable implementation for the new estimator.
Secondly, to set a high-standard for efficiency evaluation, we employ a human
expert to design best algorithms and implementations as our reference solutions
of efficiency, many of which are much more efficient than existing canonical
solutions in HumanEval and HumanEval+. Moreover, to ensure a rigorous
evaluation, we employ a human expert to curate strong test case generators to
filter out wrong code and differentiate suboptimal algorithms. An extensive
study across 30 popular LLMs using our benchmark ENAMEL shows that LLMs still
fall short of generating expert-level efficient code. Using two subsets of our
problem set, we demonstrate that such deficiency is because current LLMs
struggle in designing advanced algorithms and are barely aware of
implementation optimization. Our benchmark is publicly available at
this https URL .

本研究提出了一种评估大型语言模型在生成高效代码方面能力的高标准基准 ENAMEL，通过新的效率度量标准 eff@k 和人工专家设计的参考解决方案对 30 个常用的大型语言模型进行广泛研究，发现当前的大型语言模型在设计先进算法和实现优化方面仍有不足。