Proof Blocks

Seth Poulsen, Mahesh Viswanathan, Geoffrey Herman, Matthew West

TL;DR

Proof Blocks is a novel, autogradable tool that helps students learn mathematical proof construction by dragging and dropping pre-written lines into a logical order. By utilizing a Directed Acyclic Graph (DAG) to define statement dependencies, the tool provides instant feedback while allowing for multiple valid proof structures, effectively bridging the gap between reading a proof and writing one from scratch.

What Problem Does This Paper Address?

In discrete mathematics and computer science, writing proofs is a foundational but notoriously difficult skill. Instructors face two primary hurdles:

  1. The Feedback Gap: Proofs are traditionally graded by hand, meaning students often wait days or weeks for feedback. This delay hinders the learning cycle, especially for students who cannot attend office hours.
  2. The Scaffolding Gap: There is a massive cognitive leap between reading an instructor’s proof and staring at a blank page to write one's own.

While "Parsons Problems" (drag-and-drop code snippets) have successfully scaffolded programming education, similar tools for mathematical proofs have historically been either too rigid (limited to formal logic) or too complex (requiring students to learn heavy-duty proof assistants like Isabelle or Coq).

Methods

The authors developed Proof Blocks, a web-based interface integrated into the PrairieLearn platform.

The core technical innovation is the DAG-based grading algorithm. Instead of requiring students to match a single "master" sequence, the instructor defines a dependency graph. For example, if Statement A and Statement B are both required to prove Statement C, but A and B don't depend on each other, the student can place them in any order (A then B, or B then A) as long as both precede C.

Key features include:

  • Topological Sorting: The autograder accepts any student solution that represents a valid topological sort of the instructor's DAG.
  • Subproof Support: The tool handles complex structures like "proof by cases" or induction by requiring that lines within a specific sub-module remain contiguous, preventing nonsensical interleaving of different logical branches.
  • Distractors: Instructors can include "decoy" lines that are logically incorrect or irrelevant to increase the challenge.

Datasets

The paper evaluates the tool using data from a Fall 2020 Discrete Mathematics course at the University of Illinois at Urbana-Champaign (UIUC). The study involved over 400 students across multiple sections. The evaluation focused on student performance on exams and an anonymous survey regarding the tool's usability and perceived educational value.

Key Insights and Ideas

  • Flexibility is Key: The "aha moment" of the paper is the realization that a linear proof is just one manifestation of a non-linear dependency graph. By grading based on the graph rather than a string match, the tool respects the creative flexibility inherent in mathematical writing.
  • Scaffolding Logic over Syntax: Proof Blocks allows students to focus entirely on the logical flow and dependencies of an argument without getting bogged down in LaTeX syntax or the "blank page" paralysis.
  • Equity through Automation: Automated feedback acts as a "24/7 teaching assistant," providing support to students who may have work or family commitments that prevent them from seeking traditional in-person help.

Key Results

  • Usability: The tool was highly intuitive; 46 out of 51 surveyed students responded positively that the interface was easy to use with zero prior training.
  • Pedagogical Validity: Over two-thirds of students agreed that Proof Blocks accurately represented their understanding of how to write proofs.
  • Assessment Tiering: The authors found that Proof Blocks occupy a "middle ground" in difficulty—harder than multiple-choice questions but easier than free-response writing. This makes them an ideal formative assessment tool.
  • Adoption: Since its pilot, the tool has been integrated into the core PrairieLearn codebase and is being used by multiple universities, including the University of British Columbia and the University of Chicago.

Limitations and Future Work

  • Constraint of Pre-written Lines: The primary limitation is that students are restricted to the lines provided. They cannot yet "write" their own logic, which is the ultimate goal of proof education.
  • Instructor Overhead: The system is only as good as the instructor's DAG. If an instructor over-constrains the dependencies (e.g., making a proof strictly linear when it doesn't need to be), the tool may mark a logically sound student proof as incorrect.
  • Future Directions: The authors suggest "Faded Proof Blocks," where students are given a partial proof and must fill in the blanks, or even the automatic generation of Proof Blocks from existing mathematical text to provide students with infinite practice opportunities.

Summary updated

Abstract

In this software tool paper we present Proof Blocks, a tool which enables students to construct mathematical proofs by dragging and dropping prewritten proof lines into the correct order. We present both implementation details of the tool, as well as a rich reflection on our experiences using the tool in courses with hundreds of students. Proof Blocks problems can be graded completely automatically, enabling students to receive rapid feedback. When writing a problem, the instructor specifies the dependency graph of the lines of the proof, so that any correct arrangement of the lines can receive full credit. This innovation can improve assessment tools by increasing the types of questions we can ask students about proofs, and can give greater access to proof knowledge by increasing the amount that students can learn on their own with the help of a computer.
BibTeX
@misc{poulsen2022proof,
  author = {Seth Poulsen and Mahesh Viswanathan and Geoffrey Herman and Matthew West},
  title = {{Proof Blocks}},
  year = {2022},
  eprint = {2106.11032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.11032},
}
Figure