# Learning Randomized Reductions

arXiv: https://arxiv.org/abs/2412.18134 · HTML: https://mlsanity.com/paper/2412.18134/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Educational agents and math problem solving, one of 16 directions in LLM agents and tool use.
- Builds on 14 of its 75 references that are in the map.
- First posted on arXiv 24 Dec 2024.

## Placed in

- LLM agents and tool use / [Educational agents and math problem solving](https://mlsanity.com/agents/educational-agents-and-math-problem-solving/)

## Builds on (most cited first, 14 of 14)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [AI Feynman: a Physics-Inspired Method for Symbolic Regression](https://mlsanity.com/paper/1905.11481/) (2019)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Llemma: An Open Language Model For Mathematics](https://mlsanity.com/paper/2310.10631/) (2023)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients](https://mlsanity.com/paper/1912.04871/) (2019)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [MathPrompter: Mathematical Reasoning using Large Language Models](https://mlsanity.com/paper/2303.05398/) (2023)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity](https://mlsanity.com/paper/2006.10782/) (2020)
- [DeepMath - Deep Sequence Models for Premise Selection](https://mlsanity.com/paper/1606.04442/) (2016)
- [Globally Optimal Symbolic Regression](https://mlsanity.com/paper/1710.10720/) (2017)

## Abstract (arXiv)

Randomized self-reductions (RSRs) express f(x) using f evaluated at random correlated points, enabling self-correcting programs, instance-hiding protocols, and applications in complexity theory and cryptography. Yet discovering RSRs has required manual expert derivation for over 40 years, limiting their practical use. We present Bitween for automated RSR learning. First, we formalize RSR learning with sample complexity analysis under correlated sampling. Second, we develop Vanilla Bitween, which integrates multiple backends (linear regression, genetic programming, symbolic regression, and mixed-integer programming). The linear regression backend outperforms the others, discovering RSRs for 43 of 80 functions (54%) in RSR-Bench, our benchmark suite, including the first known reduction for sigmoid. Third, we introduce Agentic Bitween, a neuro-symbolic approach where LLM agents propose novel query functions beyond the fixed set (x+r, x-r, x · r, x, r) in prior work. Agentic Bitween discovers RSRs for 64 of 80 functions (80%), outperforming pure neural baselines in both RSR discovery and verification accuracy.