A computing resource service provider may provide computing instances organized into logical groups, such as auto-scaling groups. Computing instances assigned to an auto-scaling group may be associated with one or more load balancers configured to direct traffic to the computing instances. Furthermore, customers of the computing resource service provider may add or remove load balancer from the auto-scaling groups. The computing resource service provider may track a state of the load balancer in a database in order to enable efficient addition and removal of load balancers to auto-scale groups.