PaperlayerView exact revision on arXiv

Source-linked AI summary

TroVE: Inducing Verifiable and Efficient Toolboxes for Solving Programmatic Tasks

Zhiruo Wang, Daniel Fried, Graham Neubig

arXiv:2401.12869v1cs.AI

TL;DR

Primitive functions can produce complex, error-prone programs, while reusable high-level functions offer a way to make solutions more concise. TROVE induces and uses a toolbox of functions without training, growing and trimming it as it solves tasks. Across 11 datasets, it produces simpler, more accurate solutions than the described baselines and supports faster, more accurate human verification.

  • Problem

    Primitive functions can make program solutions complex and error-prone, while reusable higher-level functions often require expert design.

    Source: §1 · p. 1

  • Method

    TROVE induces and uses a reusable function toolbox while solving tasks, growing it over time and periodically trimming it without additional training or supervision.

    Source: §1 · p. 2

  • Results

    Across 11 datasets, TROVE produces simpler, more accurate solutions than CODELLAMA baselines and prior GPT-based methods, and human verification is 31% faster and 13% more accurate than for baseline solutions.

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

  • Takeaways & Limitations

    TROVE induces diverse functions across tasks and datasets, providing insights into their individual characteristics.

    Source: §10 · p. 9

Abstract

from arXiv · show

Language models (LMs) can solve tasks such as answering questions about tables or images by writing programs. However, using primitive functions often leads to verbose and error-prone programs, and higher-level functions require expert design. To enable better solutions without human labor, we ask code LMs to curate reusable high-level functions, and use them to write solutions. We present TROVE, a training-free method of inducing a verifiable and efficient toolbox of functions, by generating via using, growing, and periodically trimming the toolbox. On 11 datasets from math, table question answering, and image reasoning tasks, TROVE consistently yields simpler solutions with higher accuracy than baselines using CODELLAMA and previous methods using GPT, while using 79-98% smaller toolboxes. TROVE further enables 31% faster and 13% more accurate human verification than baselines. With the same pipeline, it creates diverse functions for varied tasks and datasets, providing insights into their individual characteristics.

1. Introduction

Primitive operations can make generated programs complex, error-prone, and difficult to verify, while composed functions can simplify their use. TROVE induces reusable functions while solving tasks, without additional training or supervision.

1. Introduction

  • Composed, task-aligned functions can make solutions more concise and accurate than programs assembled from primitive operations.The rate-of-change tool is easier to understand and less error-prone to use than its primitive-function counterpart.Source: §1 · p. 1
  • Prior tool-induction methods can produce large toolboxes or require added complexity and data, including training and validation datasets.CREATOR is described as producing hundreds or more tools, while other cited methods require extra datasets and auxiliary modules.Source: §1 · pp. 1–2
  • TROVE maintains and grows a toolbox while generating solutions, selects programs by execution agreement, and periodically trims low-utility functions.The method requires no additional training or supervision and selects programs using inter-execution agreement.Source: §1 · p. 2

2. Problem Statement & Baseline Methods

The paper frames program solving as having a language model compose functions to execute against an environment, with function usability affecting generation difficulty. It contrasts primitive-function and example-wise function-induction baselines.

2.1. Problem Solving via Programs

  • The setup asks a language model to compose functions into a program for a natural-language query grounded in an environment.Solutions and functions are Python programs and functions in the experiments.Source: §2.1 · p. 2
  • Primitive functions provide basic operations, but composing many of them can be error-prone; composed functions abstract those operations behind task-aligned interfaces.A wrong table row can invalidate an otherwise correct primitive solution, while composed functions hide intricate details behind an API.Source: §2.1 · p. 2
  • Because expert-crafted composed functions are costly and difficult to scale to new domains, the paper motivates creating them automatically.The stated goal is to enhance problem solving while saving human labor.Source: §2.1 · pp. 2–3

2.2. Baseline Methods

  • PRIMITIVE prompts models to write programs using primitive functions, the de facto approach without tool induction (Cheng et al., 2023; Gao et al., 2023b).Its prompt includes task instructions, primitive-function signatures and docstrings, example pairs, and the current query and environment.Source: §2.2 · p. 3
  • INSTANCE generates functions and a solution together for each example, so induced functions cannot be shared across examples.The example-wise method follows the planning/execution separation described by Qian et al. (2023); preliminary tests found joint generation comparable to sequential responses.Source: §2.2 · p. 3

3. Inducing Reusable Functions On-the-fly

TROVE processes examples online with a shared function library, generating solutions through toolbox-use modes and selecting among candidates by execution agreement and simplicity. It periodically removes functions with low usage.

3.1. Using and Growing the Toolbox

  • TROVE maintains a shared toolbox over a stream of examples, adding and removing functions as it processes examples online.The library starts empty, and the online design is intended to keep processing linear in time.Source: §3.1 · p. 3, §3 · p. 3
  • For each example, TROVE samples responses in IMPORT, CREATE, and SKIP modes, yielding 3K candidates across the three modes.IMPORT uses existing toolbox functions, CREATE adds a function, and SKIP uses primitives only.Source: §3.1 · pp. 3–4

3.2. Agreement-Based Selection

  • TROVE first removes candidates that fail execution, then favors the most frequent output and, among ties, the solution with the fewest operations.If candidates remain tied, it chooses the first in the model prediction list and adds the selected response's function to the toolbox.Source: §3.2 · p. 4

3.3. Periodic Toolbox Trimming

  • Periodic trimming removes functions used fewer than a threshold number of times, with the threshold scaled logarithmically to examples processed.The paper describes this as a way to remove low-utility functions; n denotes the number of examples processed so far.Source: §3.3 · p. 4

4. Testbeds: Program-Solvable Tasks

The testbeds cover math, table question answering, and visual reasoning, with each task given a suitable set of primitive functions and data representation.

4.1. The Default Primitive Functions

  • The experiments use Python programs, with built-in Python functions as the default primitives and task-specific additions for TableQA and VisualQA.MATH uses only the default primitives; TableQA adds pandas, while VisualQA adds image-related actions.Source: §4.1 · p. 4

4.2. Math Problems

  • MATH covers seven subjects, and its experiments use built-in Python functions while reporting test-example counts.The subjects are algebra, counting and probability, geometry, intermediate algebra, number theory, prealgebra, and precalculus.Source: §4.2 · p. 4, Table 1 · p. 4

4.3. Table Question Answering

  • TableQA uses TabMWP, WTQ, and HiTab, represents tables as pandas DataFrames, and adds pandas to the available primitives.TabMWP tables are serialized in markdown; WTQ uses DataFrame previews and CSV loading, while HiTab uses JSON parsing for hierarchical tables.Source: §4.3 · p. 5

4.4. Visual Reasoning

  • GQA provides real-world images and compositional questions, but image libraries alone yielded only 1% accuracy in preliminary experiments.The setup instead uses VisProg’s visual question answering, object-location, and crop-region actions, plus PIL.Image; omitting six other VisProg actions slightly degrades performance.Source: §4.4 · p. 5

5. Experiments

The experiments evaluate TROVE against primitive and instance-based baselines and prior tool-making methods. Across the tested tasks, TROVE generally combines higher accuracy with lower solution complexity and a small function library.

5.1. Experimental Setup

  • The setup uses CODELLAMA2-7B-INSTRUCT primarily, also tests GPT-4, runs each experiment five times, and reports the best-performing run.Prompts include c = 2 examples, sample K = 5 responses per mode, and the toolbox is trimmed every 200 steps.Source: §5.1 · p. 5

5.2. Evaluation Metrics

  • The evaluation measures exact-answer correctness, solution complexity by function-call count, and library size by additionally induced functions.Correctness and complexity are marked as metrics to maximize and minimize, respectively; library size is also minimized.Source: §5.2 · p. 6

5.3. Model Performance

  • Across the datasets, TROVE produces the most accurate solutions, generally with lower complexity and a small, efficient function library.Table 2 reports CODELLAMA results across MATH, TABLEQA, and VISUAL tasks.Source: §5.3 · p. 6
  • On seven MATH datasets, TROVE improves correctness by 30–120% over PRIMITIVE and yields 8.7–83.3% higher correctness than INSTANCE using 60.0–90.2% fewer tools.The comparisons are reported for answer correctness and tool counts, respectively.Source: §5.3 · p. 6
  • On TableQA, INSTANCE often has lower correctness than PRIMITIVE while generating hundreds or thousands of functions; on GQA, INSTANCE trails PRIMITIVE by 0.21 in correctness.The authors conjecture that too many low-utility options confuse the model, and that many GQA functions are invalid and impair solution generation.Source: §5.3 · p. 6

5.4. Comparing with Other Tool-Making Methods

  • TROVE outperforms the compared GPT-4 tool-making methods on all tested datasets and most evaluation aspects, with a simpler pipeline.The comparison covers algebra, TabMWP, and GQA, rather than all 11 datasets, because of resource limitations; Table 3 omits complexity because the prior methods do not report it.Source: §5.4 · p. 6, Table 3 · p. 6
  • GPT-4 generally outperforms CODELLAMA, but the models perform comparably on GQA; the authors relate this to familiarity with task-specific primitives.They conjecture that less-seen GQA primitives reduce GPT-4’s advantage, while 7B CODELLAMA performs on par with GPT-4 by making and reusing tools.Source: §5.4 · pp. 6–7, Table 4 · p. 7

6. Efficient Verification by Humans

A WTQ human study compares verification of solutions from PRIMITIVE, INSTANCE, and TROVE using detection accuracy and verification time.

6. Efficient Verification by Humans

  • Six evaluators checked 100 randomly selected WTQ examples, assessing whether they could identify solution correctness and how long verification took.WTQ was selected as a mid-level-difficulty representative because its TableQA functions are more complex than those in other tasks.Source: §6 · p. 7
  • TROVE reduces average verification time by 31.4% versus PRIMITIVE and 43.0% versus INSTANCE, while tool-based solutions improve detection accuracy by 13.0–14.3% over PRIMITIVE.INSTANCE’s irreusable tools increased verification time by 20.4% versus PRIMITIVE; overall, TROVE substantially speeds verification while achieving similar detection accuracy.Source: §6 · p. 7, Table 5 · p. 7

7. Inducing Specialized Functions

TROVE induces functions that vary by task and dataset, alongside shared functions, and the resulting distributions characterize their functional differences.

7. Inducing Specialized Functions

  • Across tasks, induced functions take different forms: MATH functions use external libraries or target specific problems, TableQA functions can compose many primitives, and VisualQA functions can chain few primitives.The examples include a remainder calculation for MATH, a match-after-condition function for TableQA, and an image-region function chaining object location and cropping for VisualQA.Source: §7 · p. 7, Table 6 · p. 7
  • MATH libraries share core math and sympy functions, while some functions are especially useful for particular questions, including remainder calculation and sympy.Polygen.Figure 6 illustrates the MATH libraries across seven subjects.Source: §7 · p. 7, Figure 6 · p. 8

TabMWP

  • Across the three TableQA datasets, most functions differ except for basic pandas, reflecting varied question types and table structures.Figure 7 shows functions in the three datasets.Source: §7 · pp. 7–8, Figure 7 · p. 8

7. Inducing Specialized Functions

  • TROVE induces both task-generic and domain-specific functions, which help solve problems and characterize functional distributions.The analysis uses CODELLAMA2-7B results as an example.Source: §7 · p. 7, TabMWP · p. 8

8. Ablation Studies

TROVE’s results are robust to example order across three representative datasets, while periodic trimming substantially reduces library size, with a slight degradation in accuracy and complexity when trimming is removed.

8.1. Robustness to Ordering

  • Across MATHalgebra, HiTab, and GQA, original-order results fall within randomized-order ranges, with small standard deviations and no significant variance.The study compares the original order with five shuffled orderings for each dataset.Source: §8.1 · p. 8, Table 7 · p. 8

8.2. Without Toolbox Trimming

  • In a comparison of TROVE with and without toolbox trimming, including periodic trimming reduced function-library size by 74%–90%, which the paper presents as crucial to TROVE’s efficiency.Source: §8.2 · p. 8
  • The trimming threshold and interval can be adjusted to retain more functions for diversity or fewer under constraints.The authors present trimming as a flexible efficiency–diversity choice.Source: §8.2 · p. 8

9. Related Work

Prior work generates programs from basic operations or relies on expert-designed functions, while library-abstraction and tool-induction methods have limits in applicability, reuse, or supervision. TROVE instead induces functions with LMs for general-purpose Python programs.

Generating Program Solutions

  • Program-generation work often uses basic operations or libraries, while image, audio, and video programs using task-specific functions still require expert human design.TROVE contrasts this with inducing functions using LMs to reduce human labor.Source: §9 · pp. 8–9

Domain-Specific Library Abstraction

  • Domain-specific library-abstraction methods have limited applicability to real-world tasks because general-purpose languages can vastly enlarge the search space.TROVE instead generates general-purpose Python programs and can extend to new tasks.Source: §9 · p. 9

Making Program Tools Using LLMs

  • Prior LLM tool methods variously create numerous or redundant tools, require additional training, or depend on external supervision and expert heuristics.TROVE is contrasted as using execution agreement without training or supervision.Source: §9 · p. 9

10. Conclusion

TROVE induces reusable function toolboxes for programmatic tasks and produces simpler, more accurate solutions with smaller libraries. The appendices illustrate prompt formats and define the evaluation metrics used for answer correctness and program complexity.

10. Conclusion

  • TROVE produces simpler and more accurate solutions than existing methods while using sufficiently smaller function libraries.Human verification is 31% faster and 13% more accurate; TROVE also induces diverse functions across tasks and datasets.Source: §10 · p. 9

A. Prompt Example

  • The PRIMITIVE prompt asks for a solution to the current test example, while INSTANCE prompts invite creating high-level functions for repeated actions.The ONLINE prompt modes ask for reusable functions during solution generation, make toolbox functions available, or request solutions without toolbox instructions.Source: A. Prompt Example · p. 12

B. Evaluation Metric Details

  • Answer correctness uses exact match for textual answers and rounded numerical values, accepting differences below 1e−6.Numerical answers are converted to floats and rounded to two decimals before comparison.Source: B. Evaluation Metric Details · p. 13
  • Program complexity is the summed depth of the abstract syntax trees for a solution’s expressions, treated as its number of operations.Each expression is parsed separately before its AST depth is summed.Source: B. Evaluation Metric Details · p. 13

C. Human Study: Individual Results

Individual results show that most participants verified TROVE programs fastest and more accurately than primitive-only programs. Verification times varied by participant, with one person preferring INSTANCE to PRIMITIVE.

C. Human Study: Individual Results

Loading 2401.12869v1…