PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Linear Algebra by Program Synthesis

Iddo Drori, Nakul Verma

arXiv:2111.08171v1cs.LGcs.AIcs.CL

TL;DR

Language models struggle with quantitative problems that require recursive mathematical structure. This paper turns linear-algebra questions into executable programs with Codex, achieving perfect accuracy on two course datasets.

  • Problem

    Quantitative problems remain difficult for language models, which can perform near randomly and fail even on vector-length questions; solving them often requires recursive arithmetic-expression trees.

    Source: §1 · p. 1

  • Method

    The authors turn undergraduate linear-algebra questions into programs with Codex, iteratively revising prompts and executing generated Python to obtain answers and plots.

    Source: §1 · p. 1, §3.2 · p. 3

  • Results

    Codex achieves perfect accuracy on both 30-question course datasets; one course was unavailable online and unseen during Codex training.

    Source: §1 · p. 1, §4.1 · p. 3

  • Takeaways & Limitations

    The authors say the results open the door to applying the approach to other university STEM courses, grading courses, and generating course content.

    Source: §5 · p. 4

    The pipeline does not handle input drawings or multi-line derivations and proofs, and question modification is often manual.

    Source: §4.3 · p. 4

Abstract

from arXiv · show

We solve MIT's Linear Algebra 18.06 course and Columbia University's Computational Linear Algebra COMS3251 courses with perfect accuracy by interactive program synthesis. This surprisingly strong result is achieved by turning the course questions into programming tasks and then running the programs to produce the correct answers. We use OpenAI Codex with zero-shot learning, without providing any examples in the prompts, to synthesize code from questions. We quantify the difference between the original question text and the transformed question text that yields a correct answer. Since all COMS3251 questions are not available online the model is not overfitting. We go beyond just generating code for questions with numerical answers by interactively generating code that also results visually pleasing plots as output. Finally, we automatically generate new questions given a few sample questions which may be used as new course content. This work is a significant step forward in solving quantitative math problems and opens the door for solving many university level STEM courses by machine.

1 Introduction

Quantitative problems challenge language models, and mathematical deduction often requires recursive arithmetic-expression trees. This work turns undergraduate linear-algebra questions into programming tasks and reports perfect accuracy, including on a course unseen during Codex training.

  • Language models perform near random on quantitative problems, sometimes failing even to compute a vector’s length (Hendrycks et al., 2020).Source: §1 · p. 1
  • Quantitative problems require recursive arithmetic-expression trees, a form of representation also common in program synthesis.Source: §1 · p. 1
  • The paper uses Codex, trained on text and code, to turn introductory linear-algebra problems into functions or programs that solve them.Source: §1 · p. 1
  • Codex achieves perfect accuracy on undergraduate linear-algebra problems, including a new course unavailable online and unseen during training.The approach also generates code for questions that ask for plots.Source: §1 · p. 1

2 Related Work

Prior work addresses quantitative reasoning through specialized representations and task-specific models. This paper instead explores a pretrained text-and-code foundation model for interactive linear-algebra problem solving.

  • MathBERT uses symbol and operator trees as intermediary representations for formulas (Peng et al., 2021).Source: §2 · p. 1
  • Sequence-to-sequence and graph-to-tree methods achieve around 80% on Math23k and MAWPS (Qin et al., 2020; Lan et al., 2021), while MWP-BERT achieves 96.2% on Math23k (Liang et al., 2021).Source: §2 · p. 2
  • A graph-neural-network and Transformer approach exceeds 95% accuracy on numerical machine-learning exercises but works only on its training course (Tran et al., 2021).Source: §2 · p. 2
  • This work explores a pretrained text-and-code model rather than a custom-designed solver, using the shared tree representations of questions and programs.The authors report perfect performance for interactive university-level linear-algebra problem solving and note that the model may scale across subjects without additional training.Source: §2 · p. 2

3 Methods

The methods combine program synthesis with an interactive workflow that revises questions and executes generated code. The evaluation uses two real-world university-level linear-algebra datasets, with numerical and graphical outputs.

3 Methods

  • Program synthesis generates a program with a built-in tree representation to produce a solution to the given problem.The interactive workflow also augments, rephrases, or simplifies questions with definitions and information needed for solving them.Source: §3 · p. 2

3.1 Datasets

  • The evaluation samples 30 questions each from MIT 18.06 textbook exercises and Columbia COMS3251 homework, spanning varied difficulty and output types.The questions include numerical answers and figures with multiple equations.Source: §3.1 · pp. 2–3

3.2 Interactive Workflow

  • When an initial generated program misses a projection, the authors revise the question, regenerate code, and add a plotting task so a zero vector appears visibly as a marker.Across experiments, they use fixed default davinci-codex settings: temperature 0 and response length 200.Source: §3.2 · p. 3, Figure 2 · p. 3

4 Results

Codex achieved perfect accuracy on 30 questions from each of MIT 18.06 and COMS3251, while the final programming prompts remained highly similar to the originals. The section also reports generated questions and boundaries the current pipeline does not cover.

4.1 Performance Evaluation

  • 30 questions per course were solved with perfect accuracy; GPT-3 achieved 0% accuracy.The evaluated courses were MIT 18.06 and Columbia COMS3251.Source: §4.1 · p. 3
  • 90% median cosine similarity for COMS3251 and 80% for MIT 18.06 indicate only minor changes from original questions to successful programming prompts.Figure 3 compares prompt-question similarity with the mean pairwise similarity among original questions in each course.Source: Figure 3 · p. 3, §4.1 · p. 3

4.2 Generating New Questions

  • Eight new questions were generated for each course from sample questions.Table 1 pairs the generated questions with the closest existing questions.Source: §4.2 · p. 4, Table 1 · p. 4

4.3 Limitations

  • The pipeline does not handle input drawings or other visual input, or solutions requiring multi-line derivations or proofs.The authors also report that questions are often manually modified to elicit a correct program.Source: §4.3 · p. 4

5 Conclusion

The authors present university-level linear algebra problem solving as a first step toward applying machine methods to other STEM courses and related educational tasks.

  • The authors describe their work as the first to solve university-level linear algebra problems and say it may open the door to learning STEM courses, grading courses, and generating course content automatically.Source: §5 · p. 4

A Computational Linear Algebra: Columbia University COMS3251

The appendix provides COMS3251 question-and-solution examples across several linear algebra topics, including matrix operations, systems, orthogonality, and eigenvalues.

B Introduction to Linear Algebra: MIT 18.06

The section illustrates Codex solving MIT 18.06 exercises by turning vector questions into programming tasks and executing generated code. Examples include a nontrivial linear combination, vector recovery, and plot-producing projection solutions.

Vectors and Linear Algebra

Projections

Principal Component Analysis

Loading 2111.08171v1…