Adapting, Fast and Slow: Transportable Circuits for Few-Shot Learning

Kasra Jalaldoust, Elias BareinboimSubmission to ICLR 2026 · Rejected

TL;DR

Standard domain adaptation struggles when target tasks share no direct statistical invariance with source domains. By combining causal transportability theory with circuit complexity, this paper introduces a framework that adapts to novel target distributions by composing modular causal mechanisms learned from source data. The authors show that adaptation sample complexity depends directly on the minimum circuit size needed to express the target task, and validate this with a gradient-based causal architecture.

What Problem Does This Paper Address?

In supervised domain adaptation (DA), learning in a target domain with limited data ($n$ samples) often relies on abundant source domain data ($N \gg n$). Traditional methods assume either distributional overlap (e.g., covariate shift) or strict conditional invariance ($P(Y|X)$ remains identical).

However, many real-world distribution shifts involve compositional changes: the target task may compute an entirely different overall function, yet consist of local mechanisms or subroutines that are identical to ones operating across various source domains. For example, computing a greatest common divisor (GCD) shares no global conditional distribution with tasks computing $\min$, $\max$, or subtraction, but can be computed by chaining them together. Existing causal transportability frameworks fail here because the graph and input-output mechanisms differ. The authors address how to formally license transfer of composed modules and how fast learning can proceed when domain knowledge (causal graphs and discrepancy maps) is missing.

Methods

The paper develops theory and algorithms across three tiers:

  1. Module-TR (Algorithm 1): Extends traditional transportability to settings where causal parents may differ between domains, but a discrete discrepancy oracle indicates whether the structural causal mechanism $f_Y$ is shared.
  2. Circuit-TR (Algorithm 2): Treats intermediate variables as computational nodes in a directed circuit. Given the causal DAGs and discrepancy oracle across domains, it identifies and estimates transportable local conditional distributions $P^*(V_i \mid \text{Pa}_i^*)$ from pooled source datasets, sequentially composes them, and marginalizes out intermediate variables to estimate $P^*(Y \mid X)$.
  3. Circuit-AD (Algorithm 3): A structure-agnostic algorithm for few-shot learning. Without an oracle, it enumerates candidate graph topologies and mechanism-sharing partitions, estimates candidate circuit predictors on source data, and selects the best performer using a small validation split of target data ($D^*_{\text{test}}$).
  4. Gradient-Based Approximation (Section 4 & Appendix G): To bypass the combinatorial explosion of symbolic search, the authors design a differentiable transformer-like architecture featuring:
  5. A Universal Operator Indicator (shared MLP assigning tokens to an operation from set $\mathcal{F}$).
  6. A Domain-Specific Parent Selector using causal multi-head attention with sharp temperature ($\tau = 0.1$) to identify parent nodes.
  7. An Adapter fine-tuning strategy that freezes universal operators and uses a learned gating indicator $s_i \in [0, 1]$ to decide whether each step should transport source representations or fall back on a target-only predictor.

Datasets

The evaluation is conducted on a synthetic base-10 arithmetic benchmark:

  • Sequences of length $T = 10$ and $T = 20$ executing functional programs over discrete tokens $\mathcal{V} = \{0, 1, \dots, 9\}$.
  • Variable mechanisms are randomly assigned from a library $\mathcal{F}$ of 9 null-ary, unary, and binary noisy operators: $\{g_{\text{unif}}, g_{\text{copy}}, g_{+1}, g_{-1}, g_{\times 2}, g_{\text{sum}}, g_{\text{min}}, g_{\text{subtract}}, g_{\text{mult}}\}$.
  • The paper does not evaluate on real-world datasets.

Key Insights and Ideas

  • Connecting Adaptation to Circuit Complexity: The excess risk of agnostic adaptation scales with the target SCM size $T_*$: $$\mathcal{O}\left(R_{P^*}(\mu_{\text{TR}}) + \sqrt{\frac{K \cdot T_*^3 \log T_*}{n}}\right)$$ When the target task has a small minimum circuit size $L$ over the available source basis, adaptation is fast ($O(\sqrt{1/n})$). If $L$ requires exponential unrolling (e.g., GCD using subtraction instead of modulo), adaptation degrades to slow rates requiring $n = \Omega(|\mathcal{V}|^3)$ samples.

  • Fast and Slow Adaptation Decomposition: The risk bound naturally splits: modules shared with the source decay at rate $\mathcal{O}(1/N)$ (zero-shot transfer), while novel modules decay at $\mathcal{O}(1/n)$ (slow adaptation).

  • Attention as Causal Discovery: Low-temperature causal attention heads spontaneously discover the true parent structure of the causal DAG during source pretraining.

Key Results

  • Theory: Proved that Circuit-AD achieves an excess risk that differs from the oracle-guided Circuit-TR only by a factor of $\mathcal{O}\left(\sqrt{\frac{K T_*^3 \log T_*}{n}}\right)$, which is notably independent of the vocabulary size $|\mathcal{V}|$.
  • Synthetic Experiments:
  • In sequence experiments ($T=10$, source size $N = 10^4$), pretraining successfully identified the ground-truth lower-triangular causal parent matrices.
  • With matching circuit size ($T_* = 10$), Circuit-AD significantly outperforms baselines (ERM-pool and ERM-joint) in expected NLL on held-out target data as target size $n$ ranges from 5 to 30.
  • When the circuit size is artificially constrained to $T_* = 6$ (where the full target circuit cannot be expressed), performance degrades to slow adaptation, empirically confirming the theoretical dependency on circuit capacity.

Limitations and Future Work

  • Unobserved Confounders: The main guarantees assume causal sufficiency (no hidden confounders). Appendix D shows that confounding prevents exact transportability, reducing source domain benefits to partial-transportability bounds that become obsolete once target sample size $n$ grows large.
  • Heuristic Gap: The exact symbolic algorithm (Circuit-AD) is NP-hard. While the differentiable transformer heuristic works empirically on synthetic tasks, theoretical convergence guarantees between the continuous relaxation and the symbolic optimum are left open.
  • Synthetic Scope: Experiments are strictly limited to discrete synthetic arithmetic on sequences of length 10–20; testing the paradigm on complex natural language reasoning or robotic control remains future work.

Summary updated

Abstract

Generalization across the domains is not possible without asserting a structure that constrains the unseen target domain w.r.t. the source domain. Building on causal transportability theory, we design an algorithm for zero-shot compositional generalization which relies on access to qualitative domain knowledge in form of a causal graph for intra-domain structure and discrepancies oracle for inter-domain mechanism sharing. Circuit-TR learns a collection of modules (i.e., local predictors) from the source data, and transport/compose them to obtain a circuit for prediction in the target domain if the causal structure licenses. Furthermore, circuit transportability enables us to design a supervised domain adaptation scheme that operates without access to an explicit causal structure, and instead uses limited target data. Our theoretical results characterize classes of few-shot learnable tasks in terms of graphical circuit transportability criteria, and connects few-shot generalizability with the established notion of circuit size complexity; controlled simulations corroborate our theoretical results.
BibTeX
@misc{jalaldoust2025adapting,
  author = {Kasra Jalaldoust and Elias Bareinboim},
  title = {{Adapting, Fast and Slow: Transportable Circuits for Few-Shot Learning}},
  year = {2025},
  eprint = {2512.22777},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.22777},
}
Figure