Task-switching performance is often used as a measure of executive control functions. Various task-switching studies in children with autism spectrum disorder (ASD) found, in contrast to expectations, no impairments in cognitive flexibility. Here, we studied whether the role of memory for arbitrary task rules can explain these findings, and how studying rule memory can help to generally better understand executive control. We designed a novel task-switching paradigm to separate cognitive flexibility from demand on memory for arbitrary rules, and we compared 19 children with ASD (9 to 16 years old) with an age- and IQ-matched control group. Children with ASD had increased difficulty with task switching only when memorizing arbitrary rules was required. When no arbitrary rules needed to be memorized, they performed accurately and quickly. Nevertheless, they showed less distraction from task-irrelevant stimulus features, suggesting that they represented tasks differently from the children in the comparison group. We conclude that children with ASD have a weaker capacity of forming rule representations, which only leads to performance impairment when they need to memorize arbitrary rules. Further, executive control impairments in ASD seem more complex than hitherto hypothesized due to mutual interactions between memory demand and task representations.