Brain circuits endow behavioral flexibility. Here, we study circuits encoding flexible chemotaxis in C. elegans, where the animal navigates up or down NaCl gradients (positive or negative chemotaxis) to reach the salt concentration of previous growth (the set point). The ASER sensory neuron mediates positive and negative chemotaxis by regulating the frequency and direction of reorientation movements in response to salt gradients. Both salt gradients and set point memory are encoded in ASER temporal activity patterns. Distinct temporal activity patterns in interneurons immediately downstream of ASER encode chemotactic movement decisions. Different interneuron combinations regulate positive versus negative chemotaxis. We conclude that sensorimotor pathways are segregated immediately after the primary sensory neuron in the chemotaxis circuit, and sensory representation is rapidly transformed to motor representation at the first interneuron layer. Our study reveals compact encoding of perception, memory, and locomotion in an experience-dependent navigational behavior in C. elegans.