Adding product with attributes
You're dealing with a lot of incidental complexity here. Especially extracting the product attributes from the parameters seems to be quite involved. If you have control over the form that's producing those there might be more opportunity for making things easier. As things currently are, I decided to create a factory class to allow us to break things down into smaller methods.

I didn't think deeper about the performance problem but how to structure the code in a more OO way. The main idea is to always construct a new line item and compare that to all existing line items until a match is found. The matching logic can go into the LineItem class. We can further simplify things if the LineItem could also take care about its product attributes. I punted on this and created a serialized attribute, but you might as well set up a proper association for this, maybe with a custom writer method for convenience.

Of course you need good test coverage to do a refactoring like this.

class LineItemFactory
  def self.build(parameters)
    new(parameters).build
  end

  def initialize(parameters)
    @parameters = parameters
  end

  def build
    LineItem.build(
      product: product,
      quantity: quantity,
      product_attributes: product_attributes
    )
  end

  private

  attr_reader :parameters

  def product
    @product ||= Product.find(parameters[:product_id])
  end

  def quantity
    @quantity ||= parameters[:quantity].to_i
  end

  def product_attributes
    @product_attributes ||=
      begin
        product_attributes = parameters[:line_item_attributes_attributes].try(:to_unsafe_h) || {}
        product_attributes.values.map { |attribute| attribute[:product_attribute] }
          .flatten
          .reject(&amp;:empty?)
          .map(&amp;:to_i)
      end
  end
end

class LineItem
  serialize :product_attributes
  delegate :store, to: :product

  def matches?(other)
    self.product_id == other.product_id &amp;&amp;
      self.product_attributes.sort == other.product_attributes.sort
  end
end

class Cart
  # [...]

  def add_product(parameters)
    line_item = LineItemFactory.build(parameters)
    attach_store_to_cart(line_item.store) if line_items.empty?
    existing = line_items.detect { |li| li.matches?(line_item) }
    if existing
      existing.quantity += line_item.quantity
      existing.save
    else
      line_items &lt;&lt; line_item
    end
  end

  def attach_store_to_cart(store)
    update_attribute(:store, store)
  end
end