Combining Induction and Transduction for Abstract Reasoning

Thank you for your support! We really appreciate it. Below we respond to your questions and point out to where the revised draft at the top of the page has been improved in response to your input:

What distinguishes problems suited for induction from those better addressed by transduction? Any insights into these questions would be valuable.

Great suggestion! We’ve added a full page of new experiments and analysis in the attached revision (Section 6). Briefly, as the revised abstract now says, “Inductive program synthesis excels at precise computations, and at composing multiple concepts, while transduction succeeds on fuzzier perceptual concepts.” Section 6 also has a new fine-grained analysis of how each model compares to human performance, finding that induction does surprisingly well on the problems that humans find hardest. Regarding human comparisons, we’ve improved our engineering so that—for the first time since ARC came out 5 years ago—we have a published model close to human level (54% vs 60%; see revised Section 5).

My primary concern is that the intuition behind the proposed ensemble method isn't clearly articulated

Thanks for inviting this clarification. We’ve revised to now say the following on line 142: “Induction allows checking candidate hypotheses against the training examples. Therefore, we know when induction has found a plausible solution--but sometimes it fails to find any solution. Transduction has the opposite property: We can't check if its predictions match the training examples, but it always offers a candidate answer. Therefore we ensemble by attempting induction first, then transduction if none of the candidate hypotheses explained the examples”

The revised introduction also provides related intuition (line 79): “induction and transduction can be trivially ensembled by using induction to generate candidate functions $f$ until either a satisfactory function is found (e.g. $f(x_\text{train})=y_\text{train}$) or until a test-time compute budget is reached, at which point, transduction kicks in as a fallback”

Instead of switching sequentially between these two approaches, would it be possible to develop a learning method to blend induction and transduction?

Blending induction and transduction—doing both at the same time on the same problem, possibly interleaved—is precisely the next step that we hope to pursue after this paper.

A meta-function could predict whether induction or transduction should be applied based on the input. This resulting function may provide insights into what differentiates induction-friendly tasks from transduction-friendly ones.

Definitely, it would give insight. We think though that precisely how induction and transduction complement each other makes an ensemble not need to predict which to use: Because induction can be validated by testing candidate hypotheses on the examples (but sometimes induction fails to make a prediction because no hypotheses work), while transduction can’t be validated (but it always makes a prediction), this means that you can simply try induction first, then transduction if it can’t find any hypotheses that fit the examples.

In more general settings though, there might be noise in the examples, so you don't expect to fit them perfectly. Or you might want a prior over the hypothesis space, so you won't necessarily accept something just because it fits the data. In those cases a metamodel like you suggest would make a lot of sense.

Thanks again for your support. Let us know if we can clarify anything.

Thanks for the feedback! See below for our responses, and for pointers to where we’ve revised the paper (attached at top of page) to address your concerns.

I hoped to see more in-depth analysis of why induction works better for some while transduction works better for the others

Thanks for this suggestion. We’ve added a full page of new experiments and analysis in the attached revision (Section 6). Briefly, as the revised abstract now says, “Inductive program synthesis excels at precise computations, and at composing multiple concepts, while transduction succeeds on fuzzier perceptual concepts.” Section 6 also has a new fine-grained analysis of how each model compares to human performance, and we’ve improved our work so that—for the first time since ARC came out 5 years ago—we have a published model approaching human level (see revised Section 5).

LLM often hallucinates. How do the authors quality check the generated dataset?

We do not use LLMs to predict program outputs, instead using a Python interpreter. Therefore, by construction, every program in the metalearning training data actually generates its corresponding input-outputs.

method is only tested on ARC

ARC is a composite of hundreds of tasks. Top conferences publish papers that evaluate solely on ARC (ICML ‘24, [1]; NeurIPS ‘23, [2]; NeurIPS ‘22 [3]). We increase the SOTA of open methods from 15% [1] to 54% (vs. human 60%), the first time any published method has approached human performance in the 5 years since ARC came out. Frankly, we view that empirical result as being very strong—more than enough to compensate for the lack of other benchmarks.

As reviewer aaZL says about only evaluating on ARC: “However, I'd agree with the authors that the ARC is an unsolved, challenging task, and the experiments reasonably underpin the paper's claim.”

[1] ICML ‘24, CodeIt, Butt et al.

[2] NeurIPS ‘23, ANPL, Huang et al.

[3] NeurIPS ‘22, Communicating Natural Programs, Acquaviva et al.

I wonder the conclusion would be different for some other real-world datasets.

For some datasets, like FlashFill-style text editing, previous research found induction superior [4]. In the attached updated paper, we found transduction superior on a different test set (ConceptARC). So yes, which method is best depends on the problems, and it speaks to ARC’s diversity that neither method clearly dominates.

[4] ICML ‘17, RobustFill. Devlin et al.

Dear Reviewer 22bP,

Would you mind checking out our response, and letting us know if it addresses your concerns?

In response to your review we've added a full page of new experiments/analysis. Also we've significantly improved the quantitative results.

Thank you,

Authors

Dear reviewer,

Today is the last day of reviewer discussion. Would you mind checking out our response, and new experiments?

In response to your review we've added a full page of new experiments. Also we've significantly improved the quantitative results.

Thank you, Authors

The authors partially addressed my concern but I still think some more real world test sets are needed to show the impact of the proposed method. Thus I only increase the score slightly.

Thanks for the feedback! See below for our responses, and for pointers to where we’ve revised the paper (attached) to address your concerns.

what tasks are appropriate for induction and what tasks are appropriate for transduction?

Great suggestion! We’ve added a full page of new experiments and analysis in the attached revision (Section 6). Briefly, as the revised abstract now says, “Inductive program synthesis excels at precise computations, and at composing multiple concepts, while transduction succeeds on fuzzier perceptual concepts.” Section 6 also has a new fine-grained analysis of how each model compares to human performance, finding that induction does surprisingly well on the problems that humans find hardest. Regarding human comparisons, we’ve improved our engineering so that—for the first time since ARC came out 5 years ago—we have a published model close to human level (54% vs 60%; see revised Section 5).

the author simply states that an ensemble method is proposed, but exactly how… should be elaborated

We’d specified in equation 5 how the ensembling works, but we’ve revised the text to better provide intuition. The revision now says on line 142: “Induction allows checking candidate hypotheses against the training examples. Therefore, we know when induction has found a plausible solution--but sometimes it fails to find any solution. Transduction has the opposite property: We can't check if its predictions match the training examples, but it always offers a candidate answer. Therefore we ensemble by attempting induction first, then transduction if none of the candidate hypotheses explained the examples”

The revised introduction also provides related intuition (line 79): “induction and transduction can be trivially ensembled by using induction to generate candidate functions $f$ until either a satisfactory function is found (e.g. $f(x_\text{train})=y_\text{train}$) or until a test-time compute budget is reached, at which point, transduction kicks in as a fallback”

The paper does not provide a theoretical analysis

Thanks for raising this issue. We’ve responded with a new paragraph in the discussion on line 522:

Theoretically, induction and transduction should not be so complementary. Equivalences between induction and transduction are well-know, such as the `kernel trick' which allows translating parametric function fitting into a transductive problem. Our metalearning models, given infinite metatraining data, should similarly converge because neural networks are universal function approximators. That there remains a difference is interesting precisely because it deviates from what one would expect theoretically.

overall presentation could be improved… The abstract does not summarize how the authors combine induction and transduction, nor does it provide a specific statement on the differences.

Thanks for suggesting improving the abstract. It now includes the text:

“We find inductive and transductive models solve different kinds of test problems, despite having the same training problems and sharing the same neural architecture: Inductive program synthesis excels at precise computations, and at composing multiple concepts, while transduction succeeds on fuzzier perceptual concepts. Ensembling them approaches human-level performance on ARC-AGI.”

the authors only conducted verification on the ARC benchmark

ARC is a composite of many tasks. Top conferences publish papers that evaluate solely on ARC (ICML ‘24, [1]; NeurIPS ‘23, [2]; NeurIPS ‘22 [3]). We increase the SOTA of open methods from 15% [1] to 54% (vs. human 60%), the first time any published method has approached human performance in the 5 years ARC has been out. Frankly, we view that empirical result as being very strong—more than enough to compensate for the lack of other benchmarks.

As reviewer aaZL says regarding only evaluating on ARC: “However, I'd agree with the authors that the ARC is an unsolved, challenging task, and the experiments reasonably underpin the paper's claim.”

[1] ICML ‘24, CodeIt, Butt et al.

[2] NeurIPS ‘23, ANPL, Huang et al.

[3] NeurIPS ‘22, Communicating Natural Programs, Acquaviva et al.

Would the reviewer still have rejected this paper if the application was Go instead of ARC? All three of the reviewer's concerns could have been raise for the AlphaGo paper (Silver et al. 2016 in Nature). Specifically, AlphaGo

• did not have theoretical analysis,
• used many tricks that were orthogonal to their main method (MCTS with a learned value function),
• did not evaluate on "real-world tasks" outside of the "grid world" (the Go board).

These concerns are completely valid. However, rejecting the paper solely based on these concerns feels extreme.

To be honest, I had the same concerns about AlphaGo when it first came out in 2016. I was especially concerned whether their findings could be relevant beyond games. However, this concern is exactly why such papers should be published, because then others can build on them. It took the community many years to build upon those findings from Go, poker, Dota and Diplomacy, before we arrived at o1. Human-level accuracy on ARC is not AGI, just like AlphaGo was not. Probably few of us would be "convinced that AGI can be achieved at the grid world level." But that doesn't mean there's nothing to learn here.

Thanks for your continued engagement.

It seems our only remaining disagreement is whether our conclusions apply to other domains. Although lines 510-520 gave various examples, but to focus just on those you mention:

how could researchers apply your insights when working on other tasks, such as Atari or Omniglot?

For Omniglot we predict alphabets with counting (eg Braille) or significant compositionality (eg Hangul) favor induction. We predict cursive English favors transduction (fine-grained perception).

For Atari we’d expect inductive search for policies to succeed where successful play requires precise tracking of cause-effect dependencies, like Montezuma’s revenge (counting # of keys). Transduction make sense for games like Pitfall, which demand fast perception-action mapping based on what is immediately perceived around the player. Note this goes against conventional wisdom, which lumps those games together.

You’re of course correct our conclusions are empirical, and we prove no theorem separating transductive and inductive generalization (in fact, it seems theoretically unjustified: L522). But should the paper be rejected over this?

Finally, we do appreciate you encouraging further discussion of how the general insights apply to other datasets. The final version will include the above discussion of Atari and Omniglot.

Thanks a lot for your support! Below we respond to your questions and point out relevant changes in the posted revision.

a categorization of the problems they can solve seems to be missing. Adding some minimal insight into this could enhance the papers impact.

Great suggestion! We’ve added a full page of new experiments and analysis in the attached revision (Section 6). Briefly, as the revised abstract now says, “Inductive program synthesis excels at precise computations, and at composing multiple concepts, while transduction succeeds on fuzzier perceptual concepts.” Section 6 also has a new fine-grained analysis of how each model compares to human performance, finding that induction does surprisingly well on the problems that humans find hardest. Regarding human comparisons, we’ve improved our engineering so that—for the first time since ARC came out 5 years ago—we have a published model close to human level (54% vs 60%; see revised Section 5).

The authors' definition seems to blur the line between induction and transduction, as their definition of induction forms the hypothesis based on the train examples and the test example, which classically would be considered transduction

Good point! Our reasoning was that the induction model serves as a proposal distribution, so (1) in the infinite-sample limit, the exact form of the distribution shouldn’t matter, and (2) the samples are filtered (reweighed) using only the training input-outputs, not the test input. You’re of course correct though that conditioning hypothesis generation on the test input is nonstandard, and it does blur the line between induction and transduction, because we’re never actually in the infinite-sample limit.

How are the grids that are inputs to the ARC problem encoded

We’ve added the following text (line 157): “We encode 2D colored grids as strings using 1 token per pixel, and use newlines to delimit rows (Appendix B.1).” Appendix B.1 now reads: “We must include in our prompts for our fine-tuned models the input/output 2D colored grids of each problem. To do this we represent the problem textually by naming the colors one-by-one. We renamed certain colors which were more than one token (e.g., maroon$\to$brown saves 1 token/pixel), and presented the grid as a whitespace-delimited 2D array with newlines delimiting rows. Please see below [which shows illustrated examples]”

Thanks again for your support. Let us know if we can clarify anything.