PaperlayerView exact revision on arXiv

Source-linked AI summary

DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks

Kaijie Zhu, Jiaao Chen, Jindong Wang, Neil Zhenqiang Gong, Diyi Yang, Xing Xie

arXiv:2309.17167v3cs.AIcs.CLcs.LG

TL;DR

Existing LLM benchmarks may be contaminated and remain fixed in complexity as models advance. DYVAL dynamically generates graph-informed reasoning evaluations with controllable complexity; experiments report worsening performance as difficulty rises and potential benefits from using its samples for fine-tuning.

  • Problem

    Existing benchmarks may overlap with LLM training data and typically have fixed complexity, limiting evaluation as model capabilities advance.

    Source: §1 · pp. 1–2

  • Method

    DYVAL dynamically generates evaluation samples under constraints, using directed acyclic graphs to compose reasoning tasks and natural-language descriptions.

    Source: §1 · p. 2

  • Results

    As DYVAL difficulty increases, LLMs tend to perform worse and their performance gap becomes larger; DYVAL results also do not always align with existing benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DYVAL-generated samples can serve as both evaluation sets and fine-tuning data, with the authors reporting improved performance on existing benchmarks after fine-tuning.

    Source: §6 · p. 9

    The study focuses on reasoning tasks, uses a limited number of test samples, and leaves broader fine-tuning evaluations for future work.

    Source: §6 · p. 9

Abstract

from arXiv · show

Large language models (LLMs) have achieved remarkable performance in various evaluation benchmarks. However, concerns are raised about potential data contamination in their considerable volume of training corpus. Moreover, the static nature and fixed complexity of current benchmarks may inadequately gauge the advancing capabilities of LLMs. In this paper, we introduce DyVal, a general and flexible protocol for dynamic evaluation of LLMs. Based on our framework, we build graph-informed DyVal by leveraging the structural advantage of directed acyclic graphs to dynamically generate evaluation samples with controllable complexities. DyVal generates challenging evaluation sets on reasoning tasks including mathematics, logical reasoning, and algorithm problems. We evaluate various LLMs ranging from Flan-T5-large to GPT-3.5-Turbo and GPT-4. Experiments show that LLMs perform worse in DyVal-generated evaluation samples with different complexities, highlighting the significance of dynamic evaluation. We also analyze the failure cases and results of different prompting methods. Moreover, DyVal-generated samples are not only evaluation sets, but also helpful data for fine-tuning to improve the performance of LLMs on existing benchmarks. We hope that DyVal can shed light on future evaluation research of LLMs. Code is available at: https://github.com/microsoft/promptbench.

1 INTRODUCTION

Existing benchmarks may be contaminated and fixed in complexity, limiting evaluation as LLMs advance. DYVAL dynamically generates reasoning samples, and experiments report performance gaps and potential fine-tuning benefits.

Motivation

  • Existing benchmarks may overlap with training data and use fixed complexity, while crowd-sourced dynamic benchmarks can be expensive and tedious.These issues motivate evaluation that can adapt sample generation and complexity as models advance.Source: §1 · pp. 1–2

Approach

  • DYVAL dynamically generates samples using generation algorithm G, constraints C for complexity and validity, and description function F for natural-language rendering.The graph-informed approach uses directed acyclic graphs to compose seven reasoning problems across mathematics, logic, and algorithms.Source: §1 · pp. 2–3

Experiments

  • The paper evaluates multiple LLMs and prompting methods, conducts a human study, and tests DYVAL-generated data as fine-tuning data.The evaluation includes seven reasoning tasks and 82 human evaluators; the authors also report experiments on existing benchmarks.Source: §1 · p. 2

Key findings

  • As difficulty increases, LLMs tend to perform worse and their performance gap becomes larger, while DYVAL-generated data improved Llama2 results on six existing benchmarks.The authors also report that results on DYVAL are not always consistent with existing benchmarks and that no prompting method performs best across all evaluation sets.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses LLM evaluation, contamination, and compositional task construction through benchmarks, human or crowd-sourced testing, and specialized methods. DYVAL is presented as a dynamic protocol for LLM reasoning evaluation, distinct in both objective and methodology.

Evaluating LLMs

  • DYVAL introduces a dynamic evaluation system focused on reasoning tasks, complementing established evaluation approaches and specialized benchmarks.The authors distinguish it from Krause et al. (2018), who introduced the term “dynamic evaluation,” by its approach and goals.Source: §2 · p. 3

Data Contamination

  • DYVAL is a protocol to mitigate contamination concerns, not a method for detecting contamination in LLMs.Prior work discussed contamination risks and designed detection methods, which the authors distinguish from DYVAL’s role.Source: §2 · p. 3

Complex-to-simple problem decomposition and evaluation set construction

  • Unlike graph-based work on GNN benchmarks, DYVAL uses graph structure to construct reasoning tasks for LLM evaluation.The authors situate its methodology alongside decomposition approaches in compilers, parsing, arithmetic, and reasoning.Source: §2 · p. 3

3 DYVAL

DYVAL combines dynamic generation and controllable constraints with graph-based reasoning tasks and natural-language descriptions. Its graph structure supports adjustable complexity, while the protocol can complement existing benchmarks and has limits for tasks without well-defined structure.

3 DYVAL

  • DYVAL frames evaluation as dynamically generating samples under constraints and translating them into natural-language descriptions.The framework is described as a general protocol that can be adapted to reasoning tasks and analyzed for flexibility.Source: §3 · p. 3

3.1 GENERAL DYNAMIC EVALUATION DESCRIPTION LANGUAGE

  • The sample-generation algorithm G introduces randomness, constraints C regulate task validity and complexity, and description function F renders samples in natural language.Varying constraints permits samples at different difficulty levels; changing G and C allows different generation and complexity-control strategies.Source: §3.1 · p. 4

3.2 GRAPH-INFORMED DYNAMIC EVALUATION FOR REASONING TASKS

  • DAGs model the multistep structure of reasoning tasks and permit fine-grained difficulty control by changing graph structure.The authors describe graph-informed DYVAL as their adaptation of the general protocol for reasoning tasks.Source: §3.2 · p. 4

3.2.1 GENERATION ALGORITHM G: DAG CONSTRUCTION

  • Tree-based DAGs suit hierarchical tasks such as arithmetic and logic, while general DAGs represent complex dependencies in algorithmic challenges.Tree-based nodes represent foundational subproblems linked into a final problem; general DAGs capture non-linear relationships.Source: §3.2.1 · p. 5

3.2.2 CONSTRAINTS C FOR GRAPH GENERATION

  • Complexity constraints vary tree width and depth or general-DAG nodes and links, and can add random links or descriptions.Task constraints also specify permissible value distributions and operations, such as leaf values and allowed arithmetic operations.Source: §3.2.2 · pp. 5–6

3.2.3 DESCRIPTION FUNCTION F

  • The description function renders DAG nodes and links as natural-language sequences, with task-specific prompts defining the requested output.For arithmetic, the prompt asks for the root value; for reachability, it asks whether one randomly selected node can reach another. Node-description order can also vary.Source: §3.2.3 · p. 6

3.3 DYVAL COEXISTS AND CO-EVOLVES WITH EXISTING BENCHMARKS

  • DYVAL complements existing benchmarks and is easiest to implement for tasks with intrinsic structure; tasks without well-defined structure may be challenging.Its natural-language description function can combine with adversarial attacks or out-of-distribution prompts, and the paper reports an initial sentiment-analysis study.Source: §3.3 · p. 6

4 EXPERIMENT

GPT-4 leads on DYVAL, followed closely by GPT-3.5-Turbo, while performance generally declines as task complexity increases. The experiment also compares models with humans and examines complexity, prompting, and model-size effects.

4.1 SETUP

  • Each dataset had 500 samples evaluated three times across four complexity levels, with DAG size or tree depth and width increasing by level.For general DAGs, node counts rise from 7 to 20; tree-based DAG depth and width also vary by level.Source: §4.1 · p. 7

4.2 RESULTS FOR MATH, LOGICAL REASONING, AND ALGORITHM TASKS

  • GPT-4 leads, followed closely by GPT-3.5-Turbo; performance mostly falls from D1 to D4, and three models with strong static results perform poorly on DYVAL.The three models are phi-1.5, Xwin-13B, and WizardMath-13B.Source: §4.2 · pp. 7–8
  • On D4 mathematics and logical reasoning, GPT-4 and GPT-3.5-Turbo exceeded average human results on most tasks, though GPT-4 struggled with linear equations and abductive logic.The study recruited 82 evaluators with at least a bachelor’s degree; the results may not represent the highest level of human performance.Source: §4.2 · p. 8, Figure 3 · p. 8, §4.4 · p. 8

4.3 CASE STUDY

  • GPT-4 failures included intermediate calculation errors, faulty or self-contradictory reasoning, unsupported answers, and instruction-following errors.The analysis sampled 20 failure cases per task for arithmetic, deductive logic, abductive logic, and reachability.Source: §4.3 · p. 8, Figure 4 · p. 8

4.4 ABLATION STUDY

  • Increasing complexity reduced GPT-3.5-Turbo’s performance, with depth the predominant challenge in tree-based DAGs.The ablation varied complexity constraints across arithmetic, Boolean logic, and deductive logic.Source: §4.4 · p. 8, Figure 5 · p. 9
  • No prompting technique performed best across all tasks; APE improved linear equations by 10% but hurt deductive and abductive logic.The evaluation compared five prompting techniques on the most challenging datasets.Source: §4.4 · p. 8
  • Larger Llama2 models performed better on D1 arithmetic, Boolean logic, and reachability, but mostly did not surpass GPT-4 or humans.The model-size comparison used the simplest dataset, D1.Source: §4.4 · p. 9

5 DYVAL HELPS FINE-TUNING

The paper fine-tunes Llama2-13B-chat on DYVAL-generated reasoning data and evaluates it on generated tasks and existing benchmarks. Performance increases across tasks, including some benchmarks without directly corresponding training tasks.

5 DYVAL HELPS FINE-TUNING

  • The authors generated training data for seven tasks and fine-tuned Llama2-13B-chat, testing both training-level difficulty and harder out-of-distribution samples.They also evaluated few-shot performance on math, logical-reasoning, and algorithm benchmarks.Source: §5 · p. 9
  • The fine-tuned model improved across all tasks, including existing benchmarks GSM8K, SVAMP, FOLIO, RACO, DP, and LCS.The authors suggest similarities between the benchmarks and DYVAL-generated samples may contribute to the improvement.Source: §5 · p. 9
  • Despite having no dynamic-programming training tasks, the model improved on DP and LCS; fine-tuning GPT-3.5-Turbo did not necessarily harm natural-language understanding.Source: §5 · p. 9

6 CONCLUSION AND DISCUSSION

The conclusion and discussion reviews DyVal’s dynamically generated reasoning evaluations, their use as fine-tuning data, and noted limitations in task scope, sample size, and fine-tuning coverage. It also discusses alternative DAG description orders and the potential and verification challenges of using GPT-4 to contextualize plain problems.

6 CONCLUSION AND DISCUSSION

  • DYVAL combines graph-informed dynamic sample generation and flexible difficulty adjustment, and its generated samples can also improve LLM performance on existing benchmarks when used for fine-tuning.Figure 6 shows results on existing benchmarks for Llama2-13B-chat fine-tuned on DYVAL-generated data, but the supplied passages do not provide numerical results.Source: §6 · p. 9, Figure 6 · p. 9
  • The study focuses on reasoning tasks, uses a limited set of test samples due to resource constraints, and calls for fine-tuning experiments with more diverse models and datasets.Applying DYVAL to other tasks requires designing a task-specific generation algorithm G.Source: §6 · p. 9

B.1.1 T-DAGS

  • Tree-based DAGs are generated top-down with designated depth and width, while random intermediate-node operations and leaf values determine their computation structures.For arithmetic tasks, leaf values can be sampled from [1, 10].Source: §B.1.1 · p. 17

B.1.2 G-DAGS

  • General DAGs model interlinked relationships without a strict hierarchy, and their construction randomly assigns node values, child counts, and links.The maximum number of children depends on the input.Source: §B.1.2 · p. 17

B.2 COMPLEXITY CONTROL

  • DYVAL controls tree-DAG complexity through width, additional links, depth, and random descriptions, respectively increasing subproblem computation, inference steps, or distraction.Figure 7 illustrates four types of complexity constraints for tree-based DAGs.Source: §B.2 · p. 17, Figure 7 · p. 18

B.3 DESCRIPTION FUNCTION

  • DYVAL covers arithmetic and linear equations, Boolean, deductive, and abductive logic, and graph reachability and maximum-sum-path tasks.Linear-equation instances can derive coefficients from tree-DAG roots, requiring DAG evaluation before solving the system; maximum-sum-path tasks require considering paths and their node values.Source: §B.3 · pp. 17–18, §B.3.1 · p. 18, §B.3.2 · p. 19

B.3.3 DYVAL-A

  • The DYVAL-A prompt asks for the maximum-sum path from aaa to aae and requires the answer in <<<Answer>>> format.It defines a path’s value as the sum of its node values.Source: §B.3.3 · p. 21

B.4 DESCRIPTION ORDER

  • Three DAG description orders are considered: topological order, reversed topological order, and random order, which presents nodes without regard to dependencies.Topological order introduces nodes after their descendants; reversed order starts with outcomes and traces back to inputs.Source: §B.4 · p. 21

B.5 POTENTIALS IN USING GPT-4 TO GENERATE DESCRIPTION FUNCTIONS

  • GPT-4 can contextualize DYVAL-generated arithmetic problems, but checking whether the context and rationale are correct is difficult because errors may accumulate during problem understanding, application generation, and computation.The authors describe the approach as feasible but leave it for future work because its outputs are difficult to verify.Source: §B.5 · pp. 22–23

C PROOF

The appendix proves a lower bound on identical-DAG probability and documents the experimental setup, task prompts, and evaluation complexity levels.

C PROOF

  • For a general DAG with n nodes and at least one link per node, the lower bound on two random DAGs being identical is ((n −1)!)−1.Source: C PROOF · p. 23
  • In the one-outgoing-link case, counting yields (n −1)! distinct DAGs, so the identical-DAG probability is its inverse; operation order counts as distinct.Source: C PROOF · p. 23

D.1 EXPERIMENT ENVIRONMENT

  • Experiments used V100 16GB and A100 80GB GPUs; GPT-3.5-Turbo and GPT-4 inference used API versions gpt-3.5-turbo-0613 and gpt-4-0613.Source: §D.1 · pp. 23–24

D.2 PROMPTS

  • Math prompts specify relative-precision tolerances of 0.0001 for arithmetic and 0.001 for linear systems, with prescribed answer formats.Source: §D.2 · p. 24
  • Other prompts cover boolean, deductive, and abductive logic, reachability, and maximum-sum paths, with N/A responses where solutions cannot be determined.Source: §D.2 · pp. 24–25

D.3 EVALUATION SET

  • Evaluation complexity rises across four levels using increasing DAG node counts and link ranges, or tree-based DAG depth and width settings.For tree-based DAGs, the depth-width sequence is (2, 2), (3, 2), (3, 3), and (4, 2); greater depth requires more inference steps.Source: §D.3 · p. 25

D.4 DETAILS OF EXPERIMENT RESULTS

GPT-4 accuracy on reachability drops with reversed description order, while Llama2-13B-chat's apparent improvement with difficulty reflects random guessing.

D.4 DETAILS OF EXPERIMENT RESULTS

  • Flan-T5-large, phi-1.5, WizardMath-13B, and Xwin-13B were omitted because their performance was almost zero even on the simplest sets.Source: §D.4 · p. 25
  • Llama2-13B-chat's reachability accuracy paradoxically improves as difficulty rises, but the model essentially guesses randomly and rarely answers False.The proportion of True answers rises from 40% in D1 to 60% in D3, while non-responses elevate overall accuracy.Source: §D.4 · p. 25
  • GPT-4 reachability accuracy drops by 13.67% with reversed rather than topological description order.Source: §D.4 · p. 25

D.5 DETAILS OF CASE STUDY

This section presents case studies of GPT-4 failure modes and analyzes how complexity constraints affect GPT-3.5-Turbo performance across reasoning tasks. It also details prompting and human-study procedures, data construction, datasets, and evaluation settings for the task experiments.

D.5 DETAILS OF CASE STUDY

  • In the arithmetic example, aan is computed as aai * aak = 0.3333 * 49 = 16.3167, though the passage says it should be 16.3317; the reported aao result is 20.8167.Source: §D.5 · p. 27
  • GPT-4 can falter in interpreting abductive-logic rules and conclude that a value cannot be abduced from the given information.In one example, it answered N/A for aab after reasoning from aan being false.Source: §D.5 · pp. 27–28
  • GPT-4 sometimes makes self-contradictory assumptions within the same abductive inference.In a later example, it noted that its inference about aah contradicted its assumption in a former example.Source: §D.5 · p. 28
  • GPT-4 often gives answer-only responses without justifications, especially on algorithm tasks and occasionally on logical-reasoning tasks.The authors say these responses raise concerns about whether answers reflect comprehension or memorization.Source: §D.5 · p. 28
  • GPT-4 sometimes fails to follow intricate output instructions even when its underlying computation is sound.In one arithmetic example, it derived a complex expression but did not simplify it, although the ground truth was 11848342359.78579.Source: §D.5 · pp. 29–30

D.6 DETAILS OF VARING COMPLEXITY CONSTRAINTS

  • The complexity analysis varies depth, width, random links, and extra descriptions while holding other settings fixed across arithmetic, Boolean-logic, and deductive-logic tasks.The configurations test depth 2–6 at width 2; width 2–6 at depth 3; random links 0–4 at depth 4 and width 2; and extra descriptions 0–4 at depth 4 and width 2, with other specified additions set to zero.Source: §D.6 · pp. 30–31
  • As tree-based DAG tasks grow more intricate, LLMs struggle progressively, with depth the most influential constraint because it requires more inference steps.Source: §D.6 · p. 31

D.7 DETAILS OF PROMPT ENGINEERING

D.8 HUMAN STUDY

  • The human study followed local laws and regulations, and Table 7 reports the recruited subjects’ demographics.Source: §D.8 · p. 31, Table 7 · p. 32

E.1 CONSTRUCTING TRAINING DATA

  • Training samples pair problems with inference steps: T-DAG math and logic steps follow topological order, while algorithm steps verbalize each algorithm operation.Inference steps can be augmented with more detail, which the authors believe may benefit training.Source: §E.1 · p. 32

E.2.1 TRAINING DATA

  • For T-DAG math and logic, four training datasets each contain 500 samples at depth 3; algorithm training uses two dataset configurations.T-DAG settings vary width, random links, and random descriptions; algorithm settings use 7 nodes with up to 3 links per node or 10 nodes with up to 4.Source: §E.2.1 · p. 36

E.2.2 TESTING DATA

  • Testing data comprise ID, OOD, and OOD-hard sets; the hard sets add T-DAG links and descriptions or increase G-DAG size and connectivity.ID and OOD settings are identical here: T-DAG depth 4 and width 2, with no extra links and random descriptions; G-DAGs use 15 nodes and at most 6 links. OOD-hard uses T-DAG depth 4, width 2, one extra link per node and one random description, or G-DAGs with 20 nodes and at most 8 links.Source: §E.2.2 · p. 36
  • Evaluation used zero-shot prompting on DyVal test data and few-shot CoT examples on existing benchmarks; task results are presented in Figure 10.OOD denotes samples with differing complexity that may include more advanced structures or descriptions; benchmark contexts used 4 examples for GSM8K and SVAMP, 3 for FOLIO and RACO, and 2 for DP and LCS.Source: §E.2.2 · p. 36

E.3 RESULTS OF FINE-TUNING

Fine-tuning Llama2-13B-chat on DyVal data significantly improves boolean logic, deductive logic, and reachability, while noticeable gaps remain in mathematics, abductive logic, and max-sum path. The model was fine-tuned with LoRA for three epochs.

E.3 RESULTS OF FINE-TUNING

  • Llama2-13B-chat was fine-tuned with LoRA for 3 epochs, using rank 8, scaling factor 16, dropout 0.05, learning rate 0.0003, and batch size 128.Source: §E.3 · p. 36
  • Fine-tuning significantly improves boolean logic, deductive logic, and reachability, but noticeable gaps remain in mathematics, abductive logic, and max-sum path.The reported improvements are after fine-tuning Llama2-13B-chat on the paper's test datasets.Source: §E.3 · p. 36

F IMBALANCED GENERATED DATASET

On balanced datasets, GPT-3.5-Turbo predicts every question as True and has 50% accuracy, whereas GPT-4 maintains significantly higher accuracy across complexity levels. For arithmetic, linear equation, reachability, and max-sum-path tasks, vanilla accuracy is zero.

F IMBALANCED GENERATED DATASET

  • GPT-3.5-Turbo predicts all questions as True on balanced datasets, yielding 50% accuracy, while GPT-4 maintains significantly higher accuracy across all complexity levels.The generation process can balance labels by dropping reachability samples labeled False until a True sample is generated.Source: F IMBALANCED GENERATED DATASET · p. 36
  • Vanilla accuracy is zero for arithmetic, linear equation, reachability, and max-sum-path tasks.Source: Figure 10 · p. 37

G GENERAL LANGUAGE UNDERSTANDING ABILITY AFTER FINE-TUNING

Fine-tuning GPT-3.5-turbo-0613 on generated abductive-logic and reachability data produces mixed GLUE results: gains on CoLA, QQP, and MRPC, but declines on WNLI and QNLI. The fine-tuning data used D1–D3, while evaluation of those reasoning tasks used D4.

G GENERAL LANGUAGE UNDERSTANDING ABILITY AFTER FINE-TUNING

  • Fine-tuning improves CoLA, QQP, and MRPC results but reduces WNLI and QNLI performance.The authors report that the overall improvement across several GLUE datasets suggests fine-tuning on generated data does not necessarily hurt general language understanding.Source: G GENERAL LANGUAGE UNDERSTANDING… · p. 37
  • The fine-tuning data comprised 100 samples at each of D1, D2, and D3 for abductive logic and reachability; those tasks were tested at D4.Source: G GENERAL LANGUAGE UNDERSTANDING… · p. 37

H FLEXIBILITY TO NATURAL LANGUAGE TASKS

The paper explores extending DyVal beyond reasoning tasks through an initial sentiment-analysis experiment. For SST-2, it generates alternative sentences from syntax-tree templates and reports lower model performance on the generated samples.

H FLEXIBILITY TO NATURAL LANGUAGE TASKS

  • The authors present sentiment analysis as an initial demonstration that DyVal can extend beyond its main focus on reasoning tasks.They describe the NLP extension as nontrivial and leave further work for the future.Source: H FLEXIBILITY TO NATURAL LANGUAGE TASKS · pp. 37–38
  • For NLP, DyVal uses GPT-3.5-Turbo-extracted syntax-tree templates, replaces nouns and adjectives with alternatives, and discards replacements that shift sentence meaning.The process checks whether replacements alter the original semantic meaning.Source: H FLEXIBILITY TO NATURAL LANGUAGE TASKS · p. 37
  • Template-based graphs address grammar and naturalness constraints that make random graph generation unsuitable for natural-language samples.The templates are generated using GPT-3.5-Turbo.Source: H FLEXIBILITY TO NATURAL LANGUAGE TASKS · pp. 37–38
  • On SST-2, generated samples lowered Flan-T5-large and Llama2-7b performance versus the original dataset, indicating challenging test sets.The authors generate three alternatives per sentence and describe this as an initial study; extending DyVal to NLP is nontrivial.Source: H FLEXIBILITY TO NATURAL LANGUAGE TASKS · p. 38
Loading 2309.17167v3…