diff --git a/clang-tools-extra/pseudo/lib/GLR.cpp b/clang-tools-extra/pseudo/lib/GLR.cpp
--- a/clang-tools-extra/pseudo/lib/GLR.cpp
+++ b/clang-tools-extra/pseudo/lib/GLR.cpp
@@ -31,7 +31,6 @@
                                   const TokenStream &Tokens,
                                   const Language &Lang) {
   assert(Strategy != 0);
-  assert(Begin > 0);
   if (auto S = Lang.RecoveryStrategies.lookup(Strategy))
     return S(Begin, Tokens);
   return Token::Invalid;
@@ -614,7 +613,7 @@
   // Invariant: Heads is partitioned by source: {shifted | reduced}.
   // HeadsPartition is the index of the first head formed by reduction.
   // We use this to discard and recreate the reduced heads during recovery.
-  unsigned HeadsPartition = 0;
+  unsigned HeadsPartition = Heads.size();
   std::vector<const GSS::Node *> NextHeads;
   auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
     assert(NextHeads.empty() && "Running GC at the wrong time!");
diff --git a/clang-tools-extra/pseudo/unittests/GLRTest.cpp b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
--- a/clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -652,6 +652,31 @@
             "[  1, end) └─word := <opaque>\n");
 }
 
+TEST_F(GLRTest, RecoveryFromStartOfInput) {
+  build(R"bnf(
+    _ := start [recover=Fallback] EOF
+
+    start := IDENTIFIER
+  )bnf");
+  TestLang.Table = LRTable::buildSLR(TestLang.G);
+  bool fallback_recovered = false;
+  auto fallback = [&](Token::Index Start, const TokenStream & Code) {
+    fallback_recovered = true;
+    return Code.tokens().size();
+  };
+  TestLang.RecoveryStrategies.try_emplace(
+      extensionID("Fallback"),
+      fallback);
+  clang::LangOptions LOptions;
+  TokenStream Tokens = cook(lex("?", LOptions), LOptions);
+
+  const ForestNode &Parsed =
+      glrParse({Tokens, Arena, GSStack}, id("start"), TestLang);
+  EXPECT_TRUE(fallback_recovered);
+  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
+            "[  0, end) start := <opaque>\n");
+}
+
 TEST_F(GLRTest, RepeatedRecovery) {
   // We require multiple steps of recovery at eof and then a reduction in order
   // to successfully parse.