PaperlayerView exact revision on arXiv

Source-linked AI summary

InfoSynth: Information-Guided Benchmark Synthesis for LLMs

Ishir Garg, Neel Kolhe, Xuandong Zhao, Dawn Song

arXiv:2601.00575v2cs.CL

TL;DR

Evaluating LLM reasoning is difficult because benchmark creation and validation can be resource-intensive, and existing benchmarks may contaminate training data. InfoSynth uses embedding-based information-theoretic metrics and a seed-based, execution-verified Python problem-generation pipeline. The paper reports that its generated problems are more robust and challenging than those from prior methods, while filtering can trade difficulty for novelty and diversity.

  • Problem

    Creating and validating reasoning benchmarks can require substantial effort, and existing evaluation benchmarks may appear in LLM training data, complicating capability assessment.

    Source: §1 · p. 1

  • Method

    InfoSynth measures novelty with KL-divergence and diversity with entropy, then generates Python coding problems from seeds using genetic algorithms and iterative execution feedback.

    Source: §1 · p. 2, §3.1 · p. 2

  • Results

    InfoSynth is reported to produce more challenging and robust coding problems than previous works, while filtering improves novelty and diversity at the cost of easier problems.

    Source: §1 · p. 2, §5.1 · p. 7, §6 · p. 9

  • Takeaways & Limitations

    The framework provides an embedding-based way to assess benchmark novelty and diversity and a pipeline for generating executable, self-verified Python problems from seed data.

    Source: §1 · p. 2, §6 · p. 9

    A significant fraction of candidate problems fail self-verification, including some that are novel or non-trivial, and are filtered from the final benchmark.

    Source: §7 · p. 9

Abstract

from arXiv · show

Large language models (LLMs) have demonstrated significant advancements in reasoning and code generation, but efficiently creating new benchmarks to evaluate these capabilities remains a challenge. Traditional benchmark creation relies on manual human effort, which is expensive and time-consuming. Furthermore, existing benchmarks often contaminate LLM training data, necessitating novel and diverse benchmarks to accurately assess their genuine capabilities. This work introduces InfoSynth, a novel framework for automatically generating and evaluating reasoning benchmarks guided by information-theoretic principles. We propose metrics based on KL-divergence and entropy to quantify benchmark novelty and diversity without relying on costly model evaluations. Building on this framework, we develop an end-to-end pipeline that synthesizes robust Python coding problems from seed datasets using genetic algorithms and iterative code feedback. Our method generates accurate test cases and solutions to new problems 97% of the time, and the synthesized benchmarks consistently exhibit higher difficulty compared to prior works. Moreover, our algorithm provides a method for controlling the novelty/diversity and difficulty of generated problems. InfoSynth offers a scalable, self-verifying pipeline for constructing high-quality, challenging coding benchmarks for LLMs. Project Page: https://ishirgarg.github.io/infosynth_web/

1 Introduction

Evaluating LLM reasoning remains difficult: benchmark creation and validation can demand substantial human or computational effort, while existing benchmarks may overlap with model training data. InfoSynth proposes information-theoretic assessment and a code-execution-based pipeline for generating novel, diverse, verifiably correct Python problems.

1 Introduction

  • Benchmark development and validation can require considerable human labor or computational resources, while judge LLMs may fail to solve the problems they assess.The paper focuses on Python coding problems whose solutions can be checked by execution.Source: §1 · p. 1
  • Existing benchmarks can contaminate LLM training data, and accuracy may drop by up to 8% on a novel dataset despite similar difficulty.The paper argues that new benchmarks are needed to assess model capabilities more reliably.Source: §1 · p. 1
  • The paper frames two questions: how to measure benchmark novelty and diversity, and how to generate benchmarks with those properties while ensuring correctness and robustness.It motivates these properties as relevant to reliable evaluation of LLM reasoning.Source: §1 · pp. 1–2
  • InfoSynth introduces KL-divergence and entropy metrics for comparing benchmark novelty and diversity without model evaluations, alongside an end-to-end pipeline for synthesizing Python problems.The pipeline uses genetic algorithms and iterative code feedback to produce verifiably correct problems.Source: §1 · p. 2

2 Related Work

Prior work has generated synthetic problems and unit tests, while benchmark-quality measures have assessed novelty, separability, or difficulty. InfoSynth combines executable verification with novelty and diversity analysis that does not require costly model evaluations.

Synthetic Problem Generation

Benchmark Quality Assessment

  • Existing benchmark-quality methods measure novelty, separability, or difficulty, but some rely on state-of-the-art model performance and are computationally expensive.The passage cites Li et al. (2025a,b), Truong et al. (2025), Xie et al. (2025), and Tambon et al. (2024).Source: §2 · p. 2
  • InfoSynth analyzes benchmark novelty and diversity without requiring costly model evaluations.This is presented as an alternative to quality measures that depend on model performance.Source: §2 · p. 2

3 Desirable Benchmark Properties

InfoSynth defines benchmark novelty through KL-divergence between embedding distributions and diversity through entropy. It estimates these quantities from samples and validates that their comparisons align with expected dataset relationships.

3.1 An Information-Theory Based Framework for Benchmark Analysis

  • The framework defines novelty as KL-divergence between embedding distributions and diversity as the differential entropy of a dataset's distribution.The new dataset is compared against a baseline distribution; novelty rewards mass in regions less represented by the baseline.Source: §3.1 · p. 2, §3 · p. 2
  • Because full embedding-space distributions are intractable, the framework estimates KL-divergence and entropy from samples using k-nearest-neighbor estimators.The paper identifies the estimators as those of Wang et al. (2009) and Kozachenko–Leonenko.Source: §3.1 · p. 3
  • Embedding-based KL-divergence and entropy calculations are presented as faster and cheaper than computing test-taker statistics.The authors frame these metrics as a low-cost way to estimate benchmark quality.Source: §3.1 · p. 3

3.2.1 KL-divergence Metric Validation

  • The KL-divergence comparisons align with expected novelty relationships, although the estimator can become negative when comparing a subset with its superset.The authors say this negative estimate occurs in that comparison setting and is included to show relative differences track intuition.Source: §3.2.1 · p. 3

3.2.2 Differential Entropy Metric Validation

  • Entropy comparisons show higher values for datasets expected to be more diverse.For entropy validation, the authors resample datasets to control the estimator's dataset-size effect and average the results.Source: §3.2.2 · p. 3, §3.2 · p. 3

3.3 Choosing k and d

  • For KL-divergence, the paper uses k≈4 for local differences; for entropy, larger k captures global diversity, and it recommends projecting to d∈[8, 12].The authors report consistent diversity and entropy rankings across dimensions.Source: §3.3 · p. 3

4 A Novel Benchmark Synthesis Pipeline

InfoSynth uses a genetic algorithm to generate coding problems from seed datasets, with mutation, crossover, feedback-driven verification, and deduplication. Its pipeline is designed to vary novelty, diversity, and difficulty while retaining problems that pass self-verification.

4 A Novel Benchmark Synthesis Pipeline

  • InfoSynth introduces a genetic algorithm for generating novel and diverse datasets from seed problems.The pipeline uses colonies and iterative generations, then merges and deduplicates their outputs.Source: §4 · pp. 3–4, Figure 3 · p. 5
  • The novelty comparisons report higher novelty for Leetcode than its Hash Table and String subsets, and high novelty for Leetcode and APPS relative to MBPP.The entropy comparisons describe Leetcode and APPS as spanning many CS topics, while HumanEval has lower diversity; both figures report 95% confidence intervals.Source: Figure 1 · p. 4, Figure 2 · p. 4

4.1 Data Generation Pipeline

  • Mutation generates easier, equally difficult, or harder variants, while crossover combines existing questions; k-farthest-neighbor selection retains less-similar candidates.Mutation and crossover each produce three candidates, of which the two least similar to the seed and generated set are retained.Source: §4.1 · p. 4
  • For each new problem, the model generates a Python solution and tests, executes them, and iteratively refines them using the accumulated feedback.Problems that fail self-verification are excluded from the final dataset but may seed the next generation round; generated descriptions are also postprocessed to clarify edge cases.Source: §4.1 · pp. 4–5
  • The pipeline removes textually similar problems with MinHash and LSH, using 250 permutations and a 0.75 similarity threshold.Deduplication occurs within colonies and again after their outputs are merged.Source: §4.1 · p. 5, Figure 3 · p. 5

4.2 Experimental Setup

  • The experiments create six English-language Python datasets with GPT-4o, using MBPP or Leetcode seeds and including variants without k-farthest-neighbor selection.The variants include MBPP-Guided, MBPP-Hard-Guided, Leetcode-Guided, MBPP-New, MBPP-Hard, and Leetcode-New.Source: §4.2 · p. 5

5 Results and Analysis

InfoSynth’s results examine benchmark novelty, diversity, difficulty, and generation quality across several experiments. They also compare the pipeline with prior methods and test whether topic coverage and embedding-model choice affect the findings.

5.1 Novelty and Diversity Analysis

  • Generated datasets are more novel and diverse than their seeds, but filtering and post-processing reduce novelty, and novelty can trade off against diversity and difficulty.Using all three mutation types boosts novelty, while MBPP-Hard has higher diversity than MBPP-Original; highly novel datasets tend to concentrate in low-density seed-embedding regions.Source: §5.1 · pp. 5, 7, Figure 4 · p. 7

5.2 Effect of Varying Mutation Difficulties

  • MBPP-Hard scores 8%-15% lower than MBPP-Original across most models, while its problems have reduced diversity and novelty.The results suggest mutation difficulty can be selected to control the difficulty of the generated benchmark.Source: Table 2 · p. 6, §5.2 · p. 7

5.3 Effect of Iterative Code Feedback

  • Passing solution-test pairs increase by 20% over 5 feedback iterations, while three iterations are typically ideal before further gains become marginal.Errors drop as syntax and runtime issues are fixed, although unparsable outputs rise slightly from occasional formatting failures.Source: §5.3 · p. 7

5.4 Analysis of Filtered-Out Problems

  • Filtered-out problems expose model difficulties with interacting constraints, global consistency, superficial debugging, and numerical test cases.Models may fail to produce numerical tests even when they derive correct symbolic solutions.Source: §5.4 · p. 7

5.5 Effect of the Postprocessing Step

  • Post-processing yields 5–15% accuracy gains across most test-taker models, and all 100 manually checked examples per dataset were correctly reformatted without changing the core question.The reported accuracy gains are attributed to reduced ambiguity.Source: §5.5 · p. 7, Table 3 · p. 8

5.7 Comparison to Previous Methods

  • InfoSynth generates more challenging problems than prior works, while using more input tokens but comparable expensive output-token counts.Its iterative execution-driven refinement costs about 7N input tokens; prior methods range from about 4N to 14N, with different pipeline designs.Source: Table 3 · p. 8, §5.7 · p. 8, Table 4 · p. 8

5.6 Relating Diversity and Topic Coverage

  • InfoSynth increases the number of problems covering most topics, with especially larger gains for topics less represented in original MBPP.The topic analysis used GPT-4o-mini to assign up to three topics per problem from a list drawn from Leetcode.Source: §5.6 · p. 8, Figure 5 · p. 8

5.8 Choosing an embedding model

  • Relative novelty and diversity rankings remain consistent across tested embedding models despite fluctuations in their magnitudes.The embedding-model comparison is reported in Appendix B.Source: §5.8 · p. 8

6 Conclusion

InfoSynth introduces an efficient, cost-effective framework for measuring benchmark novelty and diversity. Its coding-problem pipeline generates more challenging and robust problems from seed data than previous works.

6 Conclusion

  • InfoSynth calculates the diversity and novelty of new benchmarks efficiently and cost-effectively.This is the framework’s stated contribution.Source: §6 · p. 9
  • The coding-problem generation pipeline produces more challenging and robust problems from seed data than previous works.The conclusion states this as the pipeline’s comparative outcome.Source: §6 · p. 9
  • The authors hope future work will use these ideas to create robust, novel, and diverse benchmarks.This is presented as a future direction.Source: §6 · p. 9

7 Limitations

InfoSynth has limitations involving output-format failures, filtering of generated problems, approximate novelty and diversity metrics, and a bias toward short-horizon reasoning. The authors report empirical robustness for some aspects while identifying these boundaries for interpretation and future work.

7 Limitations

  • The evaluation focuses on Python, and some generated correct solutions fail to conform to required output formats, though deterministic checks mitigate most such cases.The authors identify improved semantic parsing as a natural extension and believe the framework can extend to other languages with executable verification.Source: §7 · p. 9
  • A significant fraction of candidates fail self-verification, including some novel or non-trivial problems; higher rejection rates correlate with greater final benchmark difficulty.The authors describe filtering as prioritizing correctness and evaluability over raw generation volume; OpenCodeInstruct has 28.2% failing solutions/tests and up to 60% of KodCode problems are filtered, while both are easier than InfoSynth.Source: §7 · p. 9
  • Novelty and diversity metrics are surrogate measures for relative comparison, not absolute Shannon entropy or KL-divergence in the original space, and lack formal theoretical guarantees.Empirically, rankings remain stable across embedding choices and hyperparameter settings.Source: §7 · p. 9
  • The filtration step biases InfoSynth toward short-horizon reasoning problems, although the resulting tasks remain challenging for frontier models.Promoting longer-horizon tasks is identified as a direction for extending beyond this regime.Source: §7 · p. 9

8 Ethical considerations

The paper reports public datasets, synthetic problem generation, and automated verification, and states that its code and datasets are open-sourced under Apache 2.0. It also notes potential risks from unfair evaluation or future training-data contamination and describes documentation as a mitigation.

8 Ethical considerations

  • InfoSynth's code and datasets are open-sourced under the Apache 2.0 license, and the work reports using publicly available datasets without private or proprietary code.The listed datasets include MBPP, Leetcode, APPS, Codeforces, and HumanEval.Source: §8 · p. 9
  • Potential risks include unfair evaluation and future contamination of model training data; the authors document the pipeline and encourage responsible use as mitigation.Source: §8 · p. 9
  • AI assistants were used only for minor grammatical improvements to the manuscript.Source: §8 · p. 10

A Sensitivity Analysis for k and UMAP Parameters

The sensitivity analysis reports robust results across a wide range of hyperparameters, with changes to novelty or diversity affecting datasets by roughly the same amount. It examines the k-NN and UMAP parameters used by the estimators.

A Sensitivity Analysis for k and UMAP Parameters

B Choice of Embedding Model

The authors test multiple embedding models and report that dataset rankings by relative novelty and diversity remain similar across models, despite fluctuations in the magnitudes of the differences.

B Choice of Embedding Model

C Algorithm For Problem Generation

The appendix lists separate generation settings for the standard and guided datasets and points to Algorithm 1 for the generation procedure.

C Algorithm For Problem Generation

D Code-Feedback Results

The code-feedback analysis tracks generated-problem outcomes across iterations and reports that more than three iterations generally provide minimal additional gains in pass rate. The section also presents the generation algorithm and figures on hyperparameter sensitivity and embedding-model invariance.

D Code-Feedback Results

  • The algorithm takes the total problem count, colony count, seed-batch size, crossover settings, and iteration count as inputs.Its parameters are N, Nc, Bs, C, Bc, and Nit.Source: D Code-Feedback Results · p. 12
  • Generation initializes an empty problem set, samples seed data for each colony, evolves each colony, deduplicates the results, and returns them.Each colony receives Ns = N/Nc problems and a random seed-data sample of size Bs.Source: D Code-Feedback Results · p. 12
  • Each generation iteration randomly selects mutation or crossover, then adds the resulting problems to the new-problem set.Mutation samples from seed data; crossover uses a batch of size Bc to produce C problems.Source: D Code-Feedback Results · p. 12
  • When enabled, k-farthest-neighbor filtering retains problems with the least cosine similarity to the combined new-problem and seed-data set.The algorithm deduplicates new problems and adds them to the seed data until the target Ns is reached.Source: D Code-Feedback Results · p. 12
  • The self-verification procedure generates tests and solutions, runs the tests, and feeds the output back to the LLM to modify them.The loop runs for Nit iterations.Source: D Code-Feedback Results · p. 12
  • Figure 6 presents a sensitivity analysis across all hyperparameters.Source: Figure 6 · p. 13
  • Figure 7 presents an embedding-model invariance analysis for the novelty and diversity metrics.Source: Figure 7 · p. 14
  • More than 3 code-feedback iterations generally provide minimal gains in pass rate across datasets.Figures 8 and 9 track the proportions of problems that pass, fail, error, or are unparsable as feedback iterations increase.Source: D Code-Feedback Results · p. 12, Figure 8 · p. 14, Figure 9 · p. 14

E Analysis of Filtered-Out Problems

This section examines filtered-out problems and related appendix components, including crossover-generated multistep coding problems, iterative solution-and-test refinement, and constrained topic labeling. Its examples show how filtering preserves major seed categories while revealing challenges in jointly generating solutions and verifiable tests, including mutation-driven changes to requirements or concepts and crossover of seed concepts.

E Analysis of Filtered-Out Problems

  • Filtering removes disproportionate numbers of deep crossover and numerically sensitive problems, while the retained dataset still covers the seed distribution’s major categories.Deep crossover tasks have tightly interacting constraints; recurrence or combinatorial tasks can elicit correct symbolic solutions but incorrect exact test values.Source: E Analysis of Filtered-Out Problems · p. 14
  • Filtered problems expose three failure patterns: incorrect test construction despite a correct solution, sequential rather than holistic constraint reasoning, and debugging loops that miss flawed strategies.Iterative feedback may stall on surface-level fixes without prompting the model to reframe its underlying approach.Source: E Analysis of Filtered-Out Problems · p. 15

H.1 Mutation Operation: Adding or Removing Constraints

  • Mutation can add or remove requirements, making harder variants demand more code or bookkeeping while retaining similar conceptual understanding.The example progresses from filtering students by age to also requiring lowercase-only profiles, then to validating passwords and student dimensions.Source: §H.1 · p. 18

H.2 Mutation Operation Example: Creative Modification

  • Mutation can also creatively change a problem’s central idea, with harder variants requiring fundamental understanding of new topics.The example moves from rectangle perimeter to area, then trapezoid area and rhombus area with a square check.Source: §H.2 · p. 18

H.3 Crossover Operation: Combining Concepts

  • Crossover combines existing concepts without introducing new ones, complementing mutation, which introduces concepts into the dataset.The example combines a strategic point-removal game with axis-aligned rectangle concepts.Source: §H.3 · p. 19

H.4 Crossover Operation: Multistep Reasoning

  • Crossover can produce multistep problems that require test-takers to solve both seed problems.Source: §H.4 · p. 20
  • The crossover example combines fourth powers of the first k odd values with XORs across selected even and final array elements, subject to k and array-count constraints.The function takes an integer array and k, with k no greater than half the array length and sufficient odd and even values required.Source: §H.4 · p. 20

I Example of Chain-of-Thought Thinking

  • Code-execution feedback prompts revisions to the solution and tests, including case-insensitive checks for all vowels and coverage of task-relevant scenarios.The example problem asks for the second-shortest string containing all vowels; feedback directs refinement of both implementation and tests.Source: I Example of Chain-of-Thought Thinking · pp. 20–21

J Topic-Labeling Prompt

  • The topic-labeling prompt limits output to three exact bank labels, prioritizing specific techniques and essential data structures without inventing tags.It asks the tagger to choose the most relevant topics for a problem and solution, include multiple essential techniques when appropriate, and return JSON only.Source: J Topic-Labeling Prompt · p. 21
Loading 2601.00575v2…