Accelerating Accurate Assignment Authoring Using Solution-Generated Autograders

AI summary

Overview

Research area: Computing education and automated assessment (submitted to arXiv under cs.CY, Computers and Society), specifically the design and large-scale deployment of autograding systems for introductory programming courses.

Technical level: Intermediate. The paper is written for computer science educators and tool builders. It assumes familiarity with basic Java/Kotlin concepts (static methods, annotations, exceptions, cyclomatic complexity) but does not require expertise in compilers, static analysis, or machine learning.

Scope: The paper introduces and evaluates "solution-generated autograding," a method that derives an accurate autograder automatically from a question author's reference solution rather than from hand-enumerated test cases, and reports four years of production experience with Questioner, a Java/Kotlin implementation used in a large CS1 course (771 questions, roughly 850,000 submissions in one term).

What This Paper Is About

Introductory programming courses benefit from large banks of practice problems, but each problem requires its own autograder, and building autograders by hand — usually by enumerating test cases in a framework like JUnit — is slow, tedious, and hard to verify for accuracy. The authors observe a key asymmetry between software testing and autograding: in autograding, the question author can supply a single correct reference solution that acts as a source of truth. Their goal is to exploit that reference solution to generate autograders automatically, quickly, and with demonstrable accuracy.

Key Contributions

1. The concept of solution-generated autograding. A framing that treats the reference solution — not a test suite — as the authority for correct behavior, and derives the autograder from it.

2. Questioner, a working implementation for Java and Kotlin. A system built around a "control class" format that bundles the problem description, configuration annotations, and reference solution into one author-provided artifact, plus a Gradle authoring plugin and a Dockerized backend service.

3. Mutation-based accuracy validation. A technique that uses source-level mutation of the reference solution to synthesize a corpus of known-incorrect submissions, then uses that corpus to empirically determine how many test iterations the autograder needs before it correctly rejects all of them — eliminating guesswork about autograder accuracy.

4. Reference-solution-derived code quality and constraint enforcement. Automatic extraction of cyclomatic complexity, executed-line count, memory allocation, submission length, dead code, and recursion status from the reference solution, used both to give students style and efficiency feedback and to block brute-force "enumerate the test cases" submissions via a complexity ceiling.

Main Findings

• Mutation removes the need for a labeled incorrect corpus. Questioner introduces small behavior-changing edits into the reference solution (e.g., < to <=, swapping && and ||) using 37 Java/Kotlin mutators from the Jeed toolkit. These mutants stand in for realistic student mistakes, so accuracy can be established without laboriously collecting and hand-labeling wrong student submissions first.

• Iteration counts become a measured quantity, not a guess. For the example "three ints strictly increasing" question, 21 iterations sufficed to distinguish all nine generated mutants, out of a possible input space of 2^96. When mutants survive past a configurable iteration limit, the author is shown the specific surviving mutant and can decide whether to suppress it (if the mutation happens to be behavior-preserving) or supply custom inputs.

• Code quality is measured against the reference solution. Questioner records cyclomatic complexity, execution time (as lines executed, which is machine-stable), memory allocated, non-comment line count, dead code, and whether methods were implemented recursively. Large deviations from the reference trigger feedback; recursion is enforced when the exercise calls for it; dead code in the reference solution causes generation to fail outright.

• A complexity cap defends against gaming. Frustrated students sometimes try to pass autograders by enumerating cases in an if-else chain rather than solving the problem. Questioner sets a submission complexity limit far above the reference solution but far below the number of autograder iterations, so such submissions are rejected immediately.

• Custom input generators are still compact. When default random generators cannot hit values like 88 or 888 in a "secret number" problem, or cannot construct a custom class, authors supply a fixed parameter list or a generator method. The authors argue this is not a return to test-case enumeration, because generators produce potentially infinite input series and correct outputs still come from the reference solution rather than hand-notated pairs.

• Class design problems are supported, not just method problems. For stateful classes, Questioner creates multiple instances, calls methods in random order with random inputs, and — importantly for debugging — reports the entire failing call sequence rather than just the final call, since a bad state update may only surface several calls later.

• Authoring throughput was high for one person. A single instructor wrote essentially the entire 771-question bank between August 2020 and August 2023, roughly one question per working day, fitting question writing into a few hours per week alongside other course duties.

• Production performance supports interactive use. In Spring 2024, Questioner handled 851,192 homework and practice submissions from 1,054 users (815 enrolled students plus several hundred course staff), with 99.96% graded successfully. Median evaluation time was 43 ms and the 99th percentile was 806 ms.

• Quiz reliability has been strong. Despite authoring hundreds of new quiz questions since 2020, the authors report never having to drop a quiz question because of autograder inaccuracy — a meaningful result given that quizzes are higher-stakes than practice work.

• Adoption generalizes beyond the originating instructor. Starting in 2023, two external instructors used Questioner to author and publish 59 questions to learncs.online, successfully adjusting problem configurations when autograder generation failed.

• Coverage spans the whole CS1 curriculum. The 771-question bank exercises all core introductory concepts; the most common Java features are declaring methods (653 questions), comparisons (618), if-else statements (515), variable operations (470), and reference equality (434). 742 questions (96%) support both Java and Kotlin.

Methodology in Plain English

The authors built a tool and then ran it in a real course, rather than running a controlled experiment. The design proceeds in a pipeline that starts from a single artifact.

An instructor writes a control class containing three things: a textual description of the problem, a small configuration annotation naming the question, and the reference solution itself. From there:

1. Figure out how to call the solution. Questioner inspects the reference solution's methods, determines what parameter types they take and what they return, and checks whether built-in random generators and equality comparators exist for those types. For the common Java types, they do.

2. Generate wrong answers by mutating the right one. Using a library of source-level mutators, it produces a set of modified versions of the solution that should behave differently. Some mutations introduce infinite loops, so timeouts also count as detectable divergence.

3. Find the smallest test budget that catches them all. It replays the same deterministic sequence of random inputs against the reference solution and each mutant, increasing the number of iterations until every mutant is flagged. If some mutant survives, the author is shown it and must intervene — by suppressing a mutation that happens to be harmless, or by adding a custom input generator.

4. Mine the solution for constraints and quality signals. Static analysis and runtime instrumentation record which classes the solution touches (so submissions can be restricted to pedagogically intended APIs), how complex it is, how much memory it allocates, how many lines it executes, whether it contains dead code, and whether methods are recursive.

5. Grade student submissions by behavioral equivalence. A submission is correct if it matches the reference solution across generated inputs in return values, thrown exception types, standard output and error, and observable state changes — while being free to implement the logic however it likes, subject to the configured constraints and quality thresholds.

The evaluation is a deployment report: bank growth over time, how questions are distributed across homework, lessons, quizzes, and practice, submission volumes and latencies from the Spring 2024 term, and external instructor adoption.

Why This Matters

Impact on research. The paper reframes autograder construction as a generative problem rather than a specification problem. It argues that the standard testing model — where tests and implementation are mutually reinforcing and neither is authoritative — is the wrong model for autograding, where the solution is authoritative. It also contributes a concrete technique (mutation-based accuracy estimation) that turns a previously unmeasurable property, autograder correctness, into a number an author can act on. The authors state they are not aware of another implementation of solution-generated autograding, though they note that bespoke autograders are common and poorly catalogued.

Real-world applications:

• University CS1 and CS2 courses needing randomized weekly quizzes, daily graded homework, and large practice banks without proportional grading staff.
• MOOC and self-study platforms where problem volume and instant feedback drive learner retention but human grading does not scale.
• K-12 and coding bootcamps introducing programming to large cohorts with limited instructor time per student.
• Corporate technical training and hiring assessments that need consistent, verifiable pass/fail judgments on coding exercises across many candidates.
• Automated evaluation of student-written tests, a side application the authors identify and begin piloting: a student test suite is correct if it distinguishes the reference solution from the same mutant corpus, which requires no extra authoring work.

Industry relevance. The efficiency and complexity constraints Questioner enforces are the same class of signals used in production code review and continuous integration (cyclomatic complexity limits, dead code detection, allocation budgets). The system's measured performance — 43 ms median grading latency across roughly 850,000 submissions on four backend servers — demonstrates that source-level analysis plus sandboxed execution is viable at interactive scale. And the ability to derive a grader from a single reference implementation has obvious analogues in automated code assessment, benchmark construction, and regression-test generation for production software, where a working reference implementation often exists but a comprehensive test suite does not.

Future Directions

1. Language portability beyond the JVM. The authors are completing Snapact, a Python implementation that follows the same approach but requires authors to supply type hints so the system knows how to generate inputs, and that lifts Questioner's one-class-per-problem restriction.

2. Grading student-written test suites. Since the mutant corpus already exists from autograder validation, the same mutants can evaluate whether a student's tests correctly separate correct from incorrect code. This was piloted in CS 124 in Fall 2024.

3. Combining with generative AI. After verifying that an LLM-produced description and reference solution are consistent, an author could feed them into solution-generated autograding to compress problem development further — making AI-generated problem drafts safe to deploy because the grader is mechanically validated rather than trusted.

4. Open questions the work leaves unresolved. Questioner does not produce minimal autograders, may misclassify adversarial submissions (the paper argues this usually indicates a student who has met the exercise's goals anyway), and compares only one JVM class per problem. Whether the approach's accuracy argument holds for problems where a reference solution is ambiguous, non-deterministic, or itself underspecified remains to be established.

Target Audience

The primary audience is computer science educators and course staff who maintain programming problem banks or teach at scale and are frustrated by the cost of writing and validating autograders. A secondary audience is autograding platform designers and researchers in computing education, for whom the solution-as-source-of-truth framing and mutation-based accuracy measurement are directly transferable ideas. Engineering teams building automated code assessment, benchmark, or regression-test infrastructure will also find the design and the complexity-based anti-gaming mechanism relevant, as will researchers applying generative AI to education, since the paper sketches how LLM-drafted problems could be made deployable through mechanical grader validation rather than blind trust.

Authors’ abstract

Students learning to program benefit from access to large numbers of practice problems. Autograders are commonly used to support programming questions by providing quick feedback on submissions. But authoring accurate autograders remains challenging. Autograders are frequently created by enumerating test cases--a tedious process that can produce inaccurate autograders that fail to correctly classify submissions. When authoring accurate autograders is slow, it is difficult to create large banks of practice problems to support beginning programmers. We present solution-generated autograding: a faster, more accurate, and more enjoyable way to create autograders. Our approach leverages a key difference between software testing and autograding: The question author can provide a solution. By starting with a solution, we can eliminate the need to manually enumerate test cases, validate the autograder's accuracy, and evaluate other aspects of submission code quality beyond behavioral correctness. We describe Questioner, an implementation of solution-generated autograding for Java and Kotlin, and share experiences from four years using Questioner to support a large CS1 course: authoring nearly 800 programming questions used by thousands of students to evaluate millions of submissions.