LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming

Sicheol Sung, Aditi, Dogyu Kim, Yo-Sub Han, Sang-Ki KoIJCAI 2025 · DOI

TL;DR

This paper introduces LogiCase, a novel framework for automatically generating effective test cases for competitive programming problems. By translating natural language problem descriptions into Context-Free Grammars with Counters (CCFGs), LogiCase generates test cases that are not only valid and specification-compliant but also adept at uncovering algorithmic flaws, outperforming existing methods.

What Problem Does This Paper Address?

Automated Test Case Generation (ATCG) is crucial for ensuring software reliability, especially in competitive programming where algorithm correctness is paramount. However, existing ATCG methods often struggle to accurately interpret complex input specifications and generate effective corner cases. This limitation hinders robust algorithm validation and can even impact program repair efforts. Current approaches, including those leveraging large language models (LLMs), frequently produce invalid or incomplete test cases due to the inherent complexity of problem constraints. The paper aims to bridge this gap by providing a scalable and reliable method for generating high-quality test cases that adhere strictly to problem specifications.

Methods

The core of LogiCase lies in its use of Context-Free Grammars with Counters (CCFGs). This formalism extends traditional Context-Free Grammars (CFGs) by incorporating counters to precisely capture numerical constraints and relationships within input specifications, which are common in competitive programming problems.

The process involves two main steps:

  1. Natural Language to CCFG Translation: A fine-tuned CodeT5 model is employed to translate natural language problem descriptions into CCFGs. This model is specifically trained to map the semantic and syntactic structures of the input specifications to the CCFG format, ensuring that the generated grammars accurately reflect the problem's logic.
  2. Test Case Generation from CCFGs: Once a CCFG is generated, it is used to systematically produce test cases. The CCFG's structure and counters guide the sampling of input values, ensuring that the generated test cases are valid, specification-compliant, and cover a range of scenarios, including corner cases.

Datasets

The primary dataset used in this work is CodeContests. This dataset comprises a diverse collection of competitive programming problems from various platforms (e.g., AtCoder, CodeChef, Codeforces). The authors also manually created CCFGs for 1,500 problems from this dataset, categorizing them by difficulty (easy, normal, hard) to facilitate model training and evaluation.

Key Insights and Ideas

  • CCFGs as a powerful formalism: The paper demonstrates that CCFGs are a significant improvement over standard CFGs for competitive programming, as they can effectively encode both syntactic and semantic aspects of input specifications, particularly numerical constraints.
  • LLMs can be guided by formal grammars: By fine-tuning CodeT5 to translate natural language into CCFGs, the authors show that LLMs can be effectively leveraged to generate formal representations, overcoming the limitations of direct prompt-based generation.
  • Grammar-based generation is robust for complex problems: LogiCase shows particular strength in handling problems with more complex input specifications, where direct LLM generation often falters.
  • Test case length matters: The study highlights that a mix of short, medium, and long test cases is more effective at identifying incorrect algorithms than relying on a single length.

Key Results

  • LogiCase, specifically the CCFGT510 model, achieved the highest set-based validity (81.18%) and effectiveness (42.26% element-based, 67.73% set-based) among the tested methods on the CodeContests dataset.
  • While direct generation from ChatGPT showed higher element-based validity (91.38%), LogiCase-generated test cases were more effective at distinguishing correct from incorrect algorithms.
  • The CCFG-based approach demonstrated a less pronounced decrease in validity as specification difficulty increased, indicating its robustness.
  • CCFGT5 generated more valid and general grammars compared to direct LLM generation methods like ChatGPT and Gemini.

Limitations and Future Work

  • Handling of natural language constraints: The paper acknowledges that the model sometimes struggles with translating natural language explanations of constraints into formal expressions, especially when the training data primarily contains explicit formal representations.
  • Inconsistent variable representation: The model occasionally conflates variables that should use counters with those that do not, due to the independent fine-tuning of grammar and constraint modules.
  • Future Work: The authors plan to expand CCFGs to handle broader input domains and optimize sampling strategies. They also suggest data augmentation and normalization to address issues with uncommon natural language expressions and inconsistent variable representations. The goal is to make LogiCase a foundation for scalable and reliable test case generation across various software engineering applications.

Summary updated

BibTeX
@inproceedings{sung2025logicase,
  author = {Sicheol Sung and Aditi and Dogyu Kim and Yo-Sub Han and Sang-Ki Ko},
  title = {{LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/861},
}
Figure