PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking Language Model Creativity: A Case Study on Code Generation

Yining Lu, Dixuan Wang, Tianjian Li, Dongwei Jiang, Sanjeev Khudanpur, Meng Jiang, Daniel Khashabi

arXiv:2407.09007v2cs.CL

TL;DR

Problem-solving creativity evaluation remains difficult because diverse solutions are hard to elicit and reliable, comprehensive measures are lacking. The paper combines iterative constraint-denial prompting with a metric for correctness, constraint adherence, and novelty against human solutions; its analysis also identifies limitations in current reasoning strategies.

  • Problem

    Problem-solving creativity evaluation is challenged by difficulty eliciting diverse solutions and the lack of reliable, comprehensive quantitative measures.

    Source: §1 · p. 1

  • Method

    The paper pairs DENIAL PROMPTING, which iteratively prohibits techniques used in prior solutions, with NEOGAUGE, which evaluates correctness, constraint adherence, and novelty against human solutions.

    Source: §1 · p. 2

  • Results

    The analysis sheds light on limitations of current reasoning strategies in improving LLM creativity.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The authors release NEOCODER to facilitate future research on LLM creativity.

    Source: §6 · p. 9

    The study is restricted to Text-to-Code because NEOGAUGE requires historical human solutions, which can be difficult to collect comprehensively for other tasks.

    Source: Limitations · p. 10

Abstract

from arXiv · show

As LLMs become increasingly prevalent, it is interesting to consider how ``creative'' these models can be. From cognitive science, creativity consists of at least two key characteristics: \emph{convergent} thinking (purposefulness to achieve a given goal) and \emph{divergent} thinking (adaptability to explore new environments or constraints) \citep{runco2003critical}. In this work, we introduce a framework for quantifying LLM creativity that incorporates the two design ingredients: (1) We introduce DENIAL PROMPTING which pushes LLMs to develop more creative solutions to a given problem by incrementally imposing new constraints on the previous solution, compelling LLMs to adopt new strategies. (2) We define NEOGAUGE, a metric that quantifies both convergent and divergent thinking in the generated creative responses by LLMs. We test the proposed framework on Codeforces problems, which serve as both a natural dataset for coding tasks and a collection of prior human solutions. We quantify NEOGAUGE for various proprietary and open-source models and find that even the most creative model, GPT-4, still falls short of demonstrating human-like creativity. We also experiment with advanced reasoning strategies (MCTS, self-correction, etc.) and observe no significant improvement in creativity. As a by-product of our analysis, we release NEOCODER dataset for reproducing our results on future models.

1 Introduction

Problem-solving creativity evaluation faces two challenges: eliciting diverse solutions and measuring creativity reliably. The paper addresses them with DENIAL PROMPTING, NEOGAUGE, and the NEOCODER benchmark.

1 Introduction

  • An automatic creativity evaluation method could help developers understand emerging model behaviors and serve as a design objective for complex real-world problems.The paper motivates evaluation as useful for both understanding and design.Source: §1 · p. 1
  • Problem-solving creativity evaluation is limited by difficulty eliciting diverse solutions and the lack of reliable, comprehensive quantitative measures.The paper frames these as two major challenges.Source: §1 · p. 1
  • DENIAL PROMPTING iteratively prohibits a technique used in the previous solution, prompting new strategies under increasingly difficult constraints.The approach aims to elicit creative generations.Source: §1 · p. 2
  • NEOGAUGE evaluates convergent creativity through correctness and constraint adherence, and divergent creativity through novelty against techniques in human solutions.This makes the evaluation state-aware and human-grounded.Source: §1 · p. 2
  • The study applies the framework to Codeforces problems, benchmarks language models, evaluates reasoning strategies, and releases the NEOCODER dataset.The dataset pairs programming problems with sequences of increasingly difficult constraints.Source: §1 · p. 2

2 Background and Related Works

Prior work has examined machine creativity and divergent-thinking measures, while problem-solving evaluation still faces challenges in eliciting creative solutions and grounding comprehensive metrics. This paper positions NEOGAUGE as measuring both feasibility and historical novelty.

Machine Creativity Evaluation

Divergent and Convergent Creative Thinking

  • Divergent thinking explores many possible uses of tools, while H-creativity additionally requires that an idea has not appeared in human history.NEOGAUGE uses historical human solutions to measure H-creativity and measures convergent creativity through correctness and constraint following.Source: §2 · p. 3

3 Constructing the NEOCODER Dataset

The NEOCODER construction pipeline applies DENIAL PROMPTING to Codeforces problems, building successive constraints from techniques detected in generated solutions. Its benchmark includes historical human solutions and test examples, and constrained generations use less common, more sophisticated techniques.

3.1 DENIAL PROMPTING: Eliciting Creative Generations from LLMs

  • DENIAL PROMPTING generates a solution, detects its atomic techniques, randomly selects a previously unused technique, and prohibits it in the updated problem.The process repeats to build a progressively larger constraint list.Source: §3.1 · p. 4

3.2 NEOCODER Dataset to Support Benchmarking LLM Creativity

  • NEOCODER uses 199 recent Codeforces problems, 30 correct human solutions per problem, and human-annotated test examples to support historical novelty and functional-correctness evaluation.GPT-4 constructs constraints for up to five iterations; dataset instances pair a problem with its constraint set.Source: §3.2 · p. 4
  • The number of problems decreases at higher constraint counts when the prompting process can no longer generate a new constraint; the existing constraint list then remains unchanged.The dataset description notes this can occur when no unused detected technique remains.Source: §3.2 · p. 5
  • As constraints accumulate, models use less common, more sophisticated techniques; without constraints, their techniques resemble common human choices.The comparison is for the top five most common techniques used by GPT-4 per state and in human solutions.Source: §3.2 · p. 5, Figure 2 · p. 5

4 State-Aware and Human-Grounded Evaluation of Machine Creativity

The section defines a state-aware evaluation of model creativity that combines constraint-following correctness with novelty relative to historical human solutions. It computes these measures for target-model outputs at successive NEOCODER constraint states.

4 State-Aware and Human-Grounded Evaluation of Machine Creativity

  • The evaluation distinguishes the target model GLM, whose creativity is assessed, from augmentation model PLM, used to construct the dataset and extract atomic techniques.For each problem and state, the corresponding NEOCODER instance is fed to GLM to obtain predictions.Source: §4 · p. 5
  • Convergent creativity measures whether generated solutions are correct and follow the constraints supplied at each state.Correctness is assessed by whether a solution passes all test examples; the state contains a specified number of distinct constraints.Source: §4 · p. 5
  • NEOGAUGE combines convergent and divergent creativity, requiring outputs to be correct, constraint-following, and H-creative.The figure illustrates why either correct constraint-following without novelty or novelty without correctness and constraint-following is insufficient.Source: §4 · pp. 5–6, Figure 3 · p. 6
  • Divergent creativity compares a model’s atomic techniques with techniques used in historical human solutions, scoring the share absent from the human set.The authors use atomic technique-level comparisons rather than sentence-level similarity and average ratios across problems.Source: §4 · p. 6

5 Experiments and Results

The experiments benchmark creativity across language models, compare LLMs with humans, and test whether reasoning strategies improve creativity. GPT-4 leads the model benchmark, but LLMs still fall short of human-like creativity, and the tested strategies provide limited overall improvement.

5.1 Experimental Setup

  • The benchmark compares GPT-4, GPT-3.5, Claude 3 Sonnet, Llama, CodeLlama, CodeGemma, and Mistral, and reports convergent, divergent, overall, and cumulative NEOGAUGE measures.NEOGAUGE@t is the joint probability of convergent and divergent creativity at state t; Figure 4 shows cumulative NEOGAUGE as the maximum creativity performance boundary.Source: §5.1 · pp. 6–7, Table 2 · p. 7

5.2 Benchmarking Language Model Creativity

  • GPT-4 has the highest NEOGAUGE at almost every state and the highest cumulative creativity boundary, ahead of smaller models.Claude-3 and Llama3-70B start close to GPT-4 at state 0, but their NEOGAUGE falls to 0 within two states.Source: Figure 4 · p. 7, §5.2 · p. 7

Which is more creative: machine or human?

  • LLMs barely exhibit human-like creativity: humans have significantly greater convergent creativity before state 3, while LLMs only minimally exceed humans’ lowest divergent creativity.Both human and LLM convergent creativity declines as state increases, consistent with a trade-off between solution quality and novelty.Source: Which is more creative: machine or… · pp. 7–8, Figure 5 · p. 8

5.3 Evaluating Reasoning Strategies for Creativity

  • The reasoning-strategy study tests MCTS, self-correction, planning, and sampling on NEOCODER, using CodeGemma-7B for MCTS and GPT-3.5 for the other strategies.For creativity evaluation, the study generates five samples per problem and reports samples with the highest convergent and divergent creativity.Source: §5.3 · pp. 8–9
  • MCTS improves divergent creativity in all five states, but its NEOGAUGE improvement is minimal and falls to 0 after t = 2; no tested strategy improves both creativity dimensions.Overall, the reasoning strategies provide limited benefit to LLM creativity.Source: §5.3 · p. 9, Figure 6 · p. 9

6 Conclusion

The conclusion presents protocols for evaluating language-model creativity in problem-solving through DENIAL PROMPTING and NEOGAUGE. It also releases NEOCODER and discusses limitations of current reasoning strategies.

6 Conclusion

  • The paper introduces DENIAL PROMPTING and NEOGAUGE as protocols for evaluating language-model creativity in problem-solving.NEOGAUGE measures convergent and divergent creativity.Source: §6 · p. 9
  • The authors release NEOCODER to facilitate future research.The dataset accompanies the proposed evaluation framework.Source: §6 · p. 9
  • The analysis sheds light on limitations of current reasoning strategies in improving LLM creativity.Source: §6 · p. 9

Limitations

The study is limited to Text-to-Code, where historical human solutions support evaluation. The authors also flag possible future-model exposure to NEOCODER problems.

Limitations

  • The study applies NEOGAUGE only to Text-to-Code because it requires historical human solutions.Collecting comprehensive sets of distinct human responses is nontrivial for most tasks in the literature.Source: Limitations · p. 10
  • Future LLMs might encounter NEOCODER’s recent Codeforces problems during pre-training.The authors suggest harder problems, higher states, or newer problem batches to mitigate this risk.Source: Limitations · p. 10

Supplemental Material

The supplemental material covers Codeforces task choice, experimental setup and results, and DENIAL PROMPTING and benchmarking prompts.

Supplemental Material

A Why Choose Codeforces for Creativity Evaluation?

The appendix argues that Codeforces problems make creativity evaluation practical through automated correctness checks and historical human solutions. It also interprets low LLM scores as a creativity gap, not an absence of valid solutions.

A Why Choose Codeforces for Creativity Evaluation?

B Experiment Setup

The human creativity evaluation measures constraint-following for convergent thinking and uses diversity among existing human solutions as a proxy for divergent thinking.

B.1 Human Creativity Evaluation

  • Human convergent creativity is measured by whether each solution’s atomic techniques follow the constraints at that state.The evaluation focuses on the constraint-following ratio.Source: §B.1 · p. 14
  • Human divergent creativity uses the same approach as Eq.3.Source: §B.1 · p. 14
  • Because collecting a human denial-prompting dataset is costly and restrictive, existing human solutions proxy divergence through each solution’s new techniques relative to the others.Eq.6 represents divergent(human, t = 0), the lowest level of human divergent creativity.Source: §B.1 · p. 14

C Experiment Results

Across states, GPT-4 generally performs best on both creativity dimensions, while benchmarking and denial prompting use the same problem-solving prompt.

C Experiment Results

  • At t=0, convergent(GPT-4, 0) = 16.16 < convergent(Llama3-70B, 0) = 19.19, though GPT-4 generally leads both measures across states.Divergent creativity remains above zero across states and can be similar for smaller models.Source: Figure 7 · p. 15, C Experiment Results · p. 15

D Prompts for DENIAL PROMPTING and Benchmarking

  • The same problem-solving prompt is used for both denial prompting and benchmarking, asking models to return a Python solve() function.The prompt instructs models to produce code intended to pass the provided test cases.Source: D Prompts for DENIAL PROMPTING and… · p. 16
  • The technique-detection prompt asks a code reviewer to identify programming techniques from a fixed list and return them as a list.Source: D Prompts for DENIAL PROMPTING and… · p. 16
  • The examples include a denial-prompting construction, a NEOCODER problem at t=5, and model outputs where CodeGemma-7B and Mistral-7B fail to parse and Llama2-70B seeks hints.Figure 9 contrasts model outputs for question 1895B at state t=5.Source: Table 4 · p. 17, Figure 9 · p. 18, Figure 8 · p. 18
Loading 2407.09007v2…