We investigate the hypothesis that human concept inference utilizes local incremental search within a compositional mental theory space. We explore this in a challenging interactive task, where participants actively gather evidence about a symbolic rule governing the behaviour of a simulated environment. Participants construct mini-experiments before making generalizations and explicit guesses about the hidden rule. They then collect additional evidence themselves (Experiment 1), observe evidence gathered by someone else (Experiment 2), or observe another learner's generalizations (Experiment 3) before revising their own generalizations and guesses. We focus on the relationship between participants' initial and revised guesses about the hidden rule concept. We find a clear order effect in which revised guesses, while influenced by new evidence, are anchored to idiosyncratic elements of the earlier guess. To capture this pattern, we develop a family of process accounts that combine program induction ideas with local (MCMC-like) adaptation mechanisms. A particularly local variant of this adaptive account captures participants' revisions better than other variants, and also beats an idealized Bayesian reasoner account, a sequential Win-Stay, Lose-Sample algorithm, and relevant baselines. We take this as suggestive that people deal with the inherent complexity of concept inference partly through use of local adaptive search in a latent compositional theory space.