diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
index 7f0d34d..fc4cd2e 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
@@ -56,6 +56,7 @@
 import com.android.tools.r8.keepanno.ast.KeepStringPattern;
 import com.android.tools.r8.keepanno.ast.KeepTarget;
 import com.android.tools.r8.keepanno.ast.KeepTypePattern;
+import com.android.tools.r8.keepanno.ast.OptionalPattern;
 import com.android.tools.r8.keepanno.ast.ParsingContext;
 import com.android.tools.r8.keepanno.ast.ParsingContext.AnnotationParsingContext;
 import com.android.tools.r8.keepanno.ast.ParsingContext.ClassParsingContext;
@@ -1331,8 +1332,7 @@
         return KeepClassItemPattern.builder()
             .setClassNamePattern(
                 classNameParser.getValueOrDefault(KeepQualifiedClassNamePattern.any()))
-            .setAnnotatedByPattern(
-                annotatedByParser.getValueOrDefault(KeepQualifiedClassNamePattern.any()))
+            .setAnnotatedByPattern(OptionalPattern.ofNullable(annotatedByParser.getValue()))
             .setInstanceOfPattern(instanceOfParser.getValueOrDefault(KeepInstanceOfPattern.any()))
             .build()
             .toClassItemReference();
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java
index 4736f07..2ecadbc 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java
@@ -22,7 +22,8 @@
 
     private KeepQualifiedClassNamePattern classNamePattern = KeepQualifiedClassNamePattern.any();
     private KeepInstanceOfPattern instanceOfPattern = KeepInstanceOfPattern.any();
-    private KeepQualifiedClassNamePattern annotatedByPattern = KeepQualifiedClassNamePattern.any();
+    private OptionalPattern<KeepQualifiedClassNamePattern> annotatedByPattern =
+        OptionalPattern.absent();
 
     private Builder() {}
 
@@ -42,7 +43,9 @@
       return this;
     }
 
-    public Builder setAnnotatedByPattern(KeepQualifiedClassNamePattern annotatedByPattern) {
+    public Builder setAnnotatedByPattern(
+        OptionalPattern<KeepQualifiedClassNamePattern> annotatedByPattern) {
+      assert annotatedByPattern != null;
       this.annotatedByPattern = annotatedByPattern;
       return this;
     }
@@ -54,12 +57,12 @@
 
   private final KeepQualifiedClassNamePattern classNamePattern;
   private final KeepInstanceOfPattern instanceOfPattern;
-  private final KeepQualifiedClassNamePattern annotatedByPattern;
+  private final OptionalPattern<KeepQualifiedClassNamePattern> annotatedByPattern;
 
   public KeepClassItemPattern(
       KeepQualifiedClassNamePattern classNamePattern,
       KeepInstanceOfPattern instanceOfPattern,
-      KeepQualifiedClassNamePattern annotatedByPattern) {
+      OptionalPattern<KeepQualifiedClassNamePattern> annotatedByPattern) {
     assert classNamePattern != null;
     assert instanceOfPattern != null;
     assert annotatedByPattern != null;
@@ -95,12 +98,12 @@
     return instanceOfPattern;
   }
 
-  public KeepQualifiedClassNamePattern getAnnotatedByPattern() {
+  public OptionalPattern<KeepQualifiedClassNamePattern> getAnnotatedByPattern() {
     return annotatedByPattern;
   }
 
   public boolean isAny() {
-    return classNamePattern.isAny() && instanceOfPattern.isAny() && annotatedByPattern.isAny();
+    return classNamePattern.isAny() && instanceOfPattern.isAny() && annotatedByPattern.isAbsent();
   }
 
   @Override
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
index 450576c..ce58000 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
@@ -17,6 +17,8 @@
  * <p>TODO(b/248408342): Update the BNF and AST to be complete.
  *
  * <pre>
+ *   OPT(T) ::= absent | present T
+ *
  *   EDGE ::= METAINFO BINDINGS PRECONDITIONS -> CONSEQUENCES
  *   METAINFO ::= [CONTEXT] [DESCRIPTION]
  *   CONTEXT ::= class-descriptor | method-descriptor | field-descriptor
@@ -42,7 +44,7 @@
  *
  *   ITEM_PATTERN ::= CLASS_ITEM_PATTERN | MEMBER_ITEM_PATTERN
  *   CLASS_ITEM_PATTERN ::= class QUALIFIED_CLASS_NAME_PATTERN
- *                              annotated-by ANNOTATED_BY_PATTERN
+ *                              annotated-by OPT(ANNOTATED_BY_PATTERN)
  *                              instance-of INSTANCE_OF_PATTERN
  *   MEMBER_ITEM_PATTERN ::= CLASS_ITEM_REFERENCE { MEMBER_PATTERN }
  *
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/OptionalPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/OptionalPattern.java
new file mode 100644
index 0000000..18061b6
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/OptionalPattern.java
@@ -0,0 +1,96 @@
+// Copyright (c) 2024, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.keepanno.ast;
+
+import java.util.function.Function;
+
+public abstract class OptionalPattern<T> {
+
+  public static <T> OptionalPattern<T> absent() {
+    return (OptionalPattern<T>) Absent.INSTANCE;
+  }
+
+  public static <T> OptionalPattern<T> of(T value) {
+    assert value != null;
+    return new Some<>(value);
+  }
+
+  public static <T> OptionalPattern<T> ofNullable(T value) {
+    return value != null ? of(value) : absent();
+  }
+
+  public abstract boolean isAbsent();
+
+  public final boolean isPresent() {
+    return !isAbsent();
+  }
+
+  public T get() {
+    throw new KeepEdgeException("Unexpected attempt to get absent value");
+  }
+
+  public <S> OptionalPattern<S> map(Function<T, S> fn) {
+    return absent();
+  }
+
+  private static final class Absent extends OptionalPattern {
+    private static final Absent INSTANCE = new Absent();
+
+    @Override
+    public boolean isAbsent() {
+      return true;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return this == obj;
+    }
+
+    @Override
+    public int hashCode() {
+      return System.identityHashCode(this);
+    }
+  }
+
+  private static final class Some<T> extends OptionalPattern<T> {
+    private final T value;
+
+    public Some(T value) {
+      this.value = value;
+    }
+
+    @Override
+    public boolean isAbsent() {
+      return false;
+    }
+
+    @Override
+    public T get() {
+      return value;
+    }
+
+    @Override
+    public <S> OptionalPattern<S> map(Function<T, S> fn) {
+      return of(fn.apply(value));
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (!(o instanceof Some)) {
+        return false;
+      }
+      Some<?> some = (Some<?>) o;
+      return value.equals(some.value);
+    }
+
+    @Override
+    public int hashCode() {
+      return value.hashCode();
+    }
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/RulePrintingUtils.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/RulePrintingUtils.java
index 4f2ee93..3e78d23 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/RulePrintingUtils.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/RulePrintingUtils.java
@@ -28,6 +28,7 @@
 import com.android.tools.r8.keepanno.ast.KeepTypePattern;
 import com.android.tools.r8.keepanno.ast.KeepUnqualfiedClassNamePattern;
 import com.android.tools.r8.keepanno.ast.ModifierPattern;
+import com.android.tools.r8.keepanno.ast.OptionalPattern;
 import com.android.tools.r8.keepanno.utils.Unimplemented;
 import java.util.List;
 import java.util.Set;
@@ -98,10 +99,11 @@
       StringBuilder builder,
       KeepClassItemPattern classPattern,
       BiConsumer<StringBuilder, KeepQualifiedClassNamePattern> printClassName) {
-    KeepQualifiedClassNamePattern annotatedByPattern = classPattern.getAnnotatedByPattern();
-    if (!annotatedByPattern.isAny()) {
+    OptionalPattern<KeepQualifiedClassNamePattern> annotatedByPattern =
+        classPattern.getAnnotatedByPattern();
+    if (annotatedByPattern.isPresent()) {
       builder.append("@");
-      printClassName(annotatedByPattern, RulePrinter.withoutBackReferences(builder));
+      printClassName(annotatedByPattern.get(), RulePrinter.withoutBackReferences(builder));
       builder.append(" ");
     }
     builder.append("class ");
diff --git a/src/test/java/com/android/tools/r8/keepanno/ClassAnnotatedByAnyAnnoPatternTest.java b/src/test/java/com/android/tools/r8/keepanno/ClassAnnotatedByAnyAnnoPatternTest.java
new file mode 100644
index 0000000..2a265db
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/keepanno/ClassAnnotatedByAnyAnnoPatternTest.java
@@ -0,0 +1,135 @@
+// Copyright (c) 2024, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndNotRenamed;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndRenamed;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.keepanno.annotations.ClassNamePattern;
+import com.android.tools.r8.keepanno.annotations.KeepConstraint;
+import com.android.tools.r8.keepanno.annotations.KeepItemKind;
+import com.android.tools.r8.keepanno.annotations.KeepTarget;
+import com.android.tools.r8.keepanno.annotations.UsedByReflection;
+import com.android.tools.r8.keepanno.annotations.UsesReflection;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableList;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class ClassAnnotatedByAnyAnnoPatternTest extends TestBase {
+
+  static final String EXPECTED = StringUtils.lines("C1: A1", "C2: A2");
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDefaultRuntimes().withApiLevel(AndroidApiLevel.B).build();
+  }
+
+  public ClassAnnotatedByAnyAnnoPatternTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(getInputClasses())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .enableExperimentalKeepAnnotations()
+        .addProgramClasses(getInputClasses())
+        .setMinApi(parameters)
+        // TODO(b/248408342): Make this implicit when annotations are kept by the keep-annotation.
+        .addKeepRuntimeVisibleAnnotations()
+        .compile()
+        .apply(b -> System.out.println(b.getProguardConfiguration()))
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(this::checkOutput);
+  }
+
+  public List<Class<?>> getInputClasses() {
+    return ImmutableList.of(
+        TestClass.class, Reflector.class, A1.class, A2.class, C1.class, C2.class, C3.class);
+  }
+
+  private void checkOutput(CodeInspector inspector) {
+    // The class constant use will ensure the annotations remains.
+    // They are not renamed as the keep-annotation will match them (they are themselves annotated).
+    assertThat(inspector.clazz(A1.class), isPresentAndNotRenamed());
+    assertThat(inspector.clazz(A2.class), isPresentAndNotRenamed());
+    // The first two classes are annotated so the keep-annotation applies and retains their name.
+    assertThat(inspector.clazz(C1.class), isPresentAndNotRenamed());
+    assertThat(inspector.clazz(C2.class), isPresentAndNotRenamed());
+    // The last class will remain due to the class constant, but it is optimized/renamed.
+    assertThat(inspector.clazz(C3.class), isPresentAndRenamed());
+  }
+
+  @Target(ElementType.TYPE)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface A1 {}
+
+  @Target(ElementType.TYPE)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface A2 {}
+
+  static class Reflector {
+
+    @UsesReflection({
+      @KeepTarget(
+          classAnnotatedByClassNamePattern = @ClassNamePattern,
+          constraints = {KeepConstraint.ANNOTATIONS, KeepConstraint.NAME}),
+    })
+    public void foo(Class<?>... classes) throws Exception {
+      for (Class<?> clazz : classes) {
+        if (clazz.getAnnotations().length > 0) {
+          String typeName = clazz.getTypeName();
+          System.out.print(typeName.substring(typeName.lastIndexOf('$') + 1) + ":");
+          if (clazz.isAnnotationPresent(A1.class)) {
+            System.out.print(" A1");
+          }
+          if (clazz.isAnnotationPresent(A2.class)) {
+            System.out.print(" A2");
+          }
+          System.out.println();
+        }
+      }
+    }
+  }
+
+  @A1
+  static class C1 {}
+
+  @A2
+  static class C2 {}
+
+  static class C3 {}
+
+  static class TestClass {
+
+    @UsedByReflection(kind = KeepItemKind.CLASS_AND_METHODS)
+    public static void main(String[] args) throws Exception {
+      new Reflector().foo(C1.class, C2.class, C3.class);
+    }
+  }
+}