Permanent invisibility increases Challenge Rating by 3.
Assuming (dis)advantage is ±5 to a roll, CR increases by 2 before accounting for the invisibility being permanent.
The conventional wisdom is that advantage and disadvantage roughly translate to a ±5 to a d20 roll (for more details see the last section of this answer). Taking this rough assumption, we can apply it to the Challenge Rating guidance found in the Dungeon Master's Guide:
Defensive Challenge Rating. [...] If your monster’s AC is at least two points higher or lower than that number, adjust the challenge rating suggested by its hit points up or down by 1 for every 2 points of difference.
Offensive Challenge Rating. [...] If your monster’s attack bonus is at least two points higher or lower than that number, adjust the challenge rating suggested by its damage output up or down by 1 for every 2 points of difference.
Assuming then that having disadvantage in attacks against the creature correlates to +5 Armor Class, and the creature having advantage on all attacks correlates to +5 to the bonus to hit, the result is a +2 to both Defensive and Offensive Challenge Rating, and since overall Challenge Rating is the average of these, we net a +2 to overall Challenge Rating. However, this is before we account for the permanency of the invisibility.
+2 CR is consistent with guidance given for similar features, but I suggest +3 because permanent invisibility is superior to these features.
Unfortunately, the Challenge Rating system doesn't encode every property of a creature. Fortunately, we have some guidance given for similar features in the Monster Features Table. The Goblin has the Nimble Escape feature, and the guidance given in the table matches the intuition I gave above:
Monster Features
Name |
Example Monster |
Effect on Challenge Rating |
Nimble Escape |
Goblin |
Increase the monster’s effective AC and effective attack bonus by 4 (assuming the monster hides every round). |
This feature allows a goblin to Hide as a bonus action each around, which can result in similar circumstances as permanent invisibility - advantage on attacks by and disadvantage on attacks against the creature:
Nimble Escape. The goblin can take the Disengage or Hide action as a bonus action on each of its turns.
This nets a +2 to Challenge Rating for the reasons described in the first section.
However, taking the Hide action requires rolling a Dexterity (Stealth) check, and so is not guaranteed to work every time. Permanent invisibility is guaranteed to work, so it is clearly superior to Nimble Escape. Additionally, permanent invisibility also provides the other potential benefit of Nimble Escape as it prevents opportunity attacks; the rules for opportunity attacks state:
You can make an opportunity attack when a hostile creature that you can see moves out of your reach.
Therefore, I suggest +3 to CR, instead of +2.