diff --git a/quiche/quic/moqt/moqt_framer.cc b/quiche/quic/moqt/moqt_framer.cc
index 6c3260c..5b54788 100644
--- a/quiche/quic/moqt/moqt_framer.cc
+++ b/quiche/quic/moqt/moqt_framer.cc
@@ -82,28 +82,34 @@
 
   size_t GetLengthOnWire() {
     size_t total = WireVarInt62(list_.size()).GetLengthOnWire();
+    uint64_t last_key = 0;
     list_.ForEach(
         [&](uint64_t key, uint64_t value) {
-          total += WireKeyVarIntPair(key, value).GetLengthOnWire();
+          total += WireKeyVarIntPair(key - last_key, value).GetLengthOnWire();
+          last_key = key;
           return true;
         },
         [&](uint64_t key, absl::string_view value) {
-          total += WireKeyStringPair(key, value).GetLengthOnWire();
+          total += WireKeyStringPair(key - last_key, value).GetLengthOnWire();
+          last_key = key;
           return true;
         });
     return total;
   }
   absl::Status SerializeIntoWriter(quiche::QuicheDataWriter& writer) {
     WireVarInt62(list_.size()).SerializeIntoWriter(writer);
+    uint64_t last_key = 0;
     list_.ForEach(
         [&](uint64_t key, uint64_t value) {
-          absl::Status status =
-              WireKeyVarIntPair(key, value).SerializeIntoWriter(writer);
+          absl::Status status = WireKeyVarIntPair(key - last_key, value)
+                                    .SerializeIntoWriter(writer);
+          last_key = key;
           return quiche::IsWriterStatusOk(status);
         },
         [&](uint64_t key, absl::string_view value) {
-          absl::Status status =
-              WireKeyStringPair(key, value).SerializeIntoWriter(writer);
+          absl::Status status = WireKeyStringPair(key - last_key, value)
+                                    .SerializeIntoWriter(writer);
+          last_key = key;
           return quiche::IsWriterStatusOk(status);
         });
     return absl::OkStatus();
@@ -250,7 +256,7 @@
         Serialize(WireVarInt62(AuthTokenAliasType::kUseValue),
                   WireVarInt62(it.type), WireBytes(it.token));
     out.insert(VersionSpecificParameter::kAuthorizationToken,
-               std::string(parameter_value.AsStringView()));
+               parameter_value.AsStringView());
   }
   if (!parameters.delivery_timeout.IsInfinite()) {
     out.insert(
diff --git a/quiche/quic/moqt/moqt_messages.cc b/quiche/quic/moqt/moqt_messages.cc
index 2283c6f..f26f172 100644
--- a/quiche/quic/moqt/moqt_messages.cc
+++ b/quiche/quic/moqt/moqt_messages.cc
@@ -9,6 +9,7 @@
 #include <cstdint>
 #include <string>
 #include <utility>
+#include <variant>
 #include <vector>
 
 #include "absl/algorithm/container.h"
@@ -23,34 +24,21 @@
 
 namespace moqt {
 
-void KeyValuePairList::insert(uint64_t key, absl::string_view value) {
-  if (key % 2 == 0) {
+void KeyValuePairList::insert(uint64_t key,
+                              std::variant<uint64_t, absl::string_view> value) {
+  if (key % 2 == 0 && std::holds_alternative<absl::string_view>(value)) {
     QUICHE_BUG(key_value_pair_string_is_even) << "Key value pair of wrong type";
     return;
   }
-  string_map_.emplace(key, value);
-}
-
-void KeyValuePairList::insert(uint64_t key, uint64_t value) {
-  if (key % 2 == 1) {
+  if (key % 2 == 1 && std::holds_alternative<uint64_t>(value)) {
     QUICHE_BUG(key_value_pair_int_is_odd) << "Key value pair of wrong type";
     return;
   }
-  integer_map_.emplace(key, value);
-}
-
-size_t KeyValuePairList::count(uint64_t key) const {
-  if (key % 2 == 0) {
-    return integer_map_.count(key);
+  if (key % 2 == 1) {
+    map_.emplace(key, std::string(std::get<absl::string_view>(value)));
+  } else {
+    map_.emplace(key, std::get<uint64_t>(value));
   }
-  return string_map_.count(key);
-}
-
-bool KeyValuePairList::contains(uint64_t key) const {
-  if (key % 2 == 0) {
-    return integer_map_.contains(key);
-  }
-  return string_map_.contains(key);
 }
 
 std::vector<uint64_t> KeyValuePairList::GetIntegers(uint64_t key) const {
@@ -59,9 +47,9 @@
     return {};
   }
   std::vector<uint64_t> result;
-  auto [range_start, range_end] = integer_map_.equal_range(key);
+  auto [range_start, range_end] = map_.equal_range(key);
   for (auto& it = range_start; it != range_end; ++it) {
-    result.push_back(it->second);
+    result.push_back(std::get<uint64_t>(it->second));
   }
   return result;
 }
@@ -73,9 +61,9 @@
     return {};
   }
   std::vector<absl::string_view> result;
-  auto [range_start, range_end] = string_map_.equal_range(key);
+  auto [range_start, range_end] = map_.equal_range(key);
   for (auto& it = range_start; it != range_end; ++it) {
-    result.push_back(it->second);
+    result.push_back(std::get<std::string>(it->second));
   }
   return result;
 }
diff --git a/quiche/quic/moqt/moqt_messages.h b/quiche/quic/moqt/moqt_messages.h
index 2308763..c55b86e 100644
--- a/quiche/quic/moqt/moqt_messages.h
+++ b/quiche/quic/moqt/moqt_messages.h
@@ -463,36 +463,36 @@
 // This class does not interpret the semantic meaning of the keys and values,
 // although it does accept various uint64_t-based enums to reduce the burden of
 // casting on the caller.
+// Keys must be ordered.
 class KeyValuePairList {
  public:
   KeyValuePairList() = default;
-  size_t size() const { return integer_map_.size() + string_map_.size(); }
-  void insert(VersionSpecificParameter key, uint64_t value) {
+  size_t size() const { return map_.size(); }
+
+  void insert(VersionSpecificParameter key,
+              std::variant<uint64_t, absl::string_view> value) {
     insert(static_cast<uint64_t>(key), value);
   }
-  void insert(SetupParameter key, uint64_t value) {
+  void insert(SetupParameter key,
+              std::variant<uint64_t, absl::string_view> value) {
     insert(static_cast<uint64_t>(key), value);
   }
-  void insert(VersionSpecificParameter key, absl::string_view value) {
-    insert(static_cast<uint64_t>(key), value);
-  }
-  void insert(SetupParameter key, absl::string_view value) {
-    insert(static_cast<uint64_t>(key), value);
-  }
-  void insert(uint64_t key, absl::string_view value);
-  void insert(uint64_t key, uint64_t value);
+  void insert(uint64_t key, std::variant<uint64_t, absl::string_view> value);
+
   size_t count(VersionSpecificParameter key) const {
-    return count(static_cast<uint64_t>(key));
+    return map_.count(static_cast<uint64_t>(key));
   }
   size_t count(SetupParameter key) const {
-    return count(static_cast<uint64_t>(key));
+    return map_.count(static_cast<uint64_t>(key));
   }
+
   bool contains(VersionSpecificParameter key) const {
-    return contains(static_cast<uint64_t>(key));
+    return map_.contains(static_cast<uint64_t>(key));
   }
   bool contains(SetupParameter key) const {
-    return contains(static_cast<uint64_t>(key));
+    return map_.contains(static_cast<uint64_t>(key));
   }
+
   // If either of these callbacks returns false, ForEach will return early.
   using IntCallback = quiche::UnretainedCallback<bool(uint64_t, uint64_t)>;
   using StringCallback =
@@ -500,13 +500,12 @@
   // Iterates through the whole list, and executes int_callback for each integer
   // value and string_callback for each string value.
   bool ForEach(IntCallback int_callback, StringCallback string_callback) const {
-    for (const auto& [key, value] : integer_map_) {
-      if (!int_callback(key, value)) {
-        return false;
-      }
-    }
-    for (const auto& [key, value] : string_map_) {
-      if (!string_callback(key, value)) {
+    for (const auto& [key, value] : map_) {
+      if (std::holds_alternative<uint64_t>(value)) {
+        if (!int_callback(key, std::get<uint64_t>(value))) {
+          return false;
+        }
+      } else if (!string_callback(key, std::get<std::string>(value))) {
         return false;
       }
     }
@@ -525,18 +524,13 @@
   std::vector<absl::string_view> GetStrings(SetupParameter key) const {
     return GetStrings(static_cast<uint64_t>(key));
   }
-  void clear() {
-    integer_map_.clear();
-    string_map_.clear();
-  }
+
+  void clear() { map_.clear(); }
 
  private:
-  size_t count(uint64_t key) const;
-  bool contains(uint64_t key) const;
   std::vector<uint64_t> GetIntegers(uint64_t key) const;
   std::vector<absl::string_view> GetStrings(uint64_t key) const;
-  absl::btree_multimap<uint64_t, uint64_t> integer_map_;
-  absl::btree_multimap<uint64_t, std::string> string_map_;
+  absl::btree_multimap<uint64_t, std::variant<uint64_t, std::string>> map_;
 };
 
 // TODO(martinduke): Collapse both Setup messages into MoqtSessionParameters.
diff --git a/quiche/quic/moqt/moqt_parser.cc b/quiche/quic/moqt/moqt_parser.cc
index 60ecf47..3017ff9 100644
--- a/quiche/quic/moqt/moqt_parser.cc
+++ b/quiche/quic/moqt/moqt_parser.cc
@@ -106,11 +106,13 @@
   if (!reader.ReadVarInt62(&num_params)) {
     return false;
   }
+  uint64_t type = 0;
   for (uint64_t i = 0; i < num_params; ++i) {
-    uint64_t type;
-    if (!reader.ReadVarInt62(&type)) {
+    uint64_t type_diff;
+    if (!reader.ReadVarInt62(&type_diff)) {
       return false;
     }
+    type += type_diff;
     if (type % 2 == 1) {
       absl::string_view bytes;
       if (!reader.ReadStringPieceVarInt62(&bytes)) {
diff --git a/quiche/quic/moqt/moqt_parser_test.cc b/quiche/quic/moqt/moqt_parser_test.cc
index c16c1a8..3af3cf0 100644
--- a/quiche/quic/moqt/moqt_parser_test.cc
+++ b/quiche/quic/moqt/moqt_parser_test.cc
@@ -494,8 +494,8 @@
       0x20, 0x00, 0x0d, 0x02, 0x01, 0x02,  // versions
       0x03,                                // 3 params
       0x01, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
-      0x02, 0x32,                          // max_request_id = 50
-      0x02, 0x32,                          // max_request_id = 50
+      0x01, 0x32,                          // max_request_id = 50
+      0x00, 0x32,                          // max_request_id = 50
   };
   stream.Receive(absl::string_view(setup, sizeof(setup)), false);
   parser.ReadAndDispatchMessages();
@@ -512,8 +512,8 @@
       0x20, 0x00, 0x13, 0x02, 0x01, 0x02,              // versions
       0x03,                                            // 3 params
       0x01, 0x03, 0x66, 0x6f, 0x6f,                    // path = "foo"
-      0x02, 0x32,                                      // max_request_id = 50
-      0x03, 0x06, 0x01, 0x10, 0x00, 0x62, 0x61, 0x72,  // REGISTER 0x01
+      0x01, 0x32,                                      // max_request_id = 50
+      0x01, 0x06, 0x01, 0x10, 0x00, 0x62, 0x61, 0x72,  // REGISTER 0x01
   };
   stream.Receive(absl::string_view(setup, sizeof(setup)), false);
   parser.ReadAndDispatchMessages();
@@ -562,7 +562,7 @@
       0x20, 0x00, 0x0e, 0x02, 0x01, 0x02,  // versions = 1, 2
       0x02,                                // 2 params
       0x01, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
-      0x01, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
+      0x00, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
   };
   stream.Receive(absl::string_view(setup, sizeof(setup)), false);
   parser.ReadAndDispatchMessages();
@@ -626,8 +626,8 @@
       0x20, 0x00, 0x0d, 0x02, 0x01, 0x02,  // versions = 1, 2
       0x03,                                // 4 params
       0x01, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
-      0x02, 0x32,                          // max_request_id = 50
-      0x02, 0x32,                          // max_request_id = 50
+      0x01, 0x32,                          // max_request_id = 50
+      0x00, 0x32,                          // max_request_id = 50
   };
   stream.Receive(absl::string_view(setup, sizeof(setup)), false);
   parser.ReadAndDispatchMessages();
@@ -659,7 +659,7 @@
       0x20, 0x00, 0x0e, 0x02, 0x01, 0x02,  // versions = 1, 2
       0x02,                                // 2 params
       0x01, 0x03, 0x66, 0x6f, 0x6f,        // path = "foo"
-      0x05, 0x03, 0x66, 0x5c, 0x6f,        // authority = "f\o"
+      0x04, 0x03, 0x66, 0x5c, 0x6f,        // authority = "f\o"
   };
   stream.Receive(absl::string_view(setup, sizeof(setup)), false);
   parser.ReadAndDispatchMessages();
@@ -679,7 +679,7 @@
       0x02,                          // filter_type = kLatestObject
       0x02,                          // two params
       0x1f, 0x03, 0x62, 0x61, 0x72,  // 0x1f = "bar"
-      0x1f, 0x03, 0x62, 0x61, 0x72,  // 0x1f = "bar"
+      0x00, 0x03, 0x62, 0x61, 0x72,  // 0x1f = "bar"
   };
   stream.Receive(absl::string_view(subscribe, sizeof(subscribe)), false);
   parser.ReadAndDispatchMessages();
@@ -697,7 +697,7 @@
       0x02,                          // filter_type = kLatestObject
       0x02,                          // two params
       0x02, 0x67, 0x10,              // delivery_timeout = 10000
-      0x02, 0x67, 0x10,              // delivery_timeout = 10000
+      0x00, 0x67, 0x10,              // delivery_timeout = 10000
   };
   stream.Receive(absl::string_view(subscribe, sizeof(subscribe)), false);
   parser.ReadAndDispatchMessages();
@@ -717,7 +717,7 @@
       0x02,                          // filter_type = kLatestObject
       0x02,                          // two params
       0x04, 0x67, 0x10,              // max_cache_duration = 10000
-      0x04, 0x67, 0x10,              // max_cache_duration = 10000
+      0x00, 0x67, 0x10,              // max_cache_duration = 10000
   };
   stream.Receive(absl::string_view(subscribe, sizeof(subscribe)), false);
   parser.ReadAndDispatchMessages();
@@ -852,7 +852,7 @@
       0x02,
       0x67,
       0x10,  // delivery_timeout = 10000 ms
-      0x03,
+      0x01,
       0x05,
       0x03,
       0x00,
@@ -896,7 +896,7 @@
       0x02,
       0x67,
       0x10,  // delivery_timeout = 10000 ms
-      0x03,
+      0x01,
       0x05,
       0x03,
       0x00,
@@ -940,7 +940,7 @@
       0x02,
       0x67,
       0x10,  // delivery_timeout = 10000 ms
-      0x03,
+      0x01,
       0x05,
       0x03,
       0x00,
@@ -964,7 +964,7 @@
       0x0c, 0x14,        // largest_group_id = 12, largest_object_id = 20,
       0x02,              // 2 parameters
       0x02, 0x67, 0x10,  // delivery_timeout = 10000
-      0x03, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization_token = "bar"
+      0x01, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization_token = "bar"
   };
   stream.Receive(absl::string_view(subscribe_ok, sizeof(subscribe_ok)), false);
   parser.ReadAndDispatchMessages();
@@ -982,7 +982,7 @@
       0x6f, 0x6f,                                // track_namespace = "foo"
       0x02,                                      // 2 params
       0x03, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization = "bar"
-      0x03, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization = "bar"
+      0x00, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization = "bar"
   };
   stream.Receive(
       absl::string_view(publish_namespace, sizeof(publish_namespace)), false);
@@ -997,8 +997,8 @@
       0x06, 0x00, 0x11, 0x02, 0x01, 0x03, 0x66,
       0x6f, 0x6f,                                // track_namespace = "foo"
       0x02,                                      // 2 params
-      0x03, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization_info = "bar"
       0x02, 0x67, 0x10,                          // delivery_timeout = 10000
+      0x01, 0x05, 0x03, 0x00, 0x62, 0x61, 0x72,  // authorization_info = "bar"
   };
   stream.Receive(
       absl::string_view(publish_namespace, sizeof(publish_namespace)), false);
diff --git a/quiche/quic/moqt/test_tools/moqt_test_message.h b/quiche/quic/moqt/test_tools/moqt_test_message.h
index 909c58a..436f720 100644
--- a/quiche/quic/moqt/test_tools/moqt_test_message.h
+++ b/quiche/quic/moqt/test_tools/moqt_test_message.h
@@ -504,9 +504,13 @@
       client_setup_.parameters.authority = "";
       raw_packet_[2] = 0x24;  // adjust payload length (-17)
       raw_packet_[6] = 0x02;  // only two parameters
+      // Move MaxRequestId up in the packet.
+      memmove(raw_packet_ + 7, raw_packet_ + 13, 2);
       // Move MoqtImplementation up in the packet.
       memmove(raw_packet_ + 9, raw_packet_ + 26,
               kTestImplementationString.length() + 2);
+      raw_packet_[7] = 0x02;  // Diff from 0.
+      raw_packet_[9] = 0x05;  // Diff from 2.
       SetWireImage(raw_packet_, sizeof(raw_packet_) - 17);
     } else {
       SetWireImage(raw_packet_, sizeof(raw_packet_));
@@ -536,7 +540,7 @@
 
   void ExpandVarints() override {
     if (!client_setup_.parameters.path.empty()) {
-      ExpandVarintsImpl("vvvvvvvv----vv---------vv---------------------------");
+      ExpandVarintsImpl("vvvvvv----vvvv---------vv---------------------------");
     } else {
       ExpandVarintsImpl("vvvvvvvv---------------------------");
     }
@@ -555,12 +559,12 @@
       0x20, 0x00, 0x35,                    // type, length
       0x02, 0x01, 0x02,                    // versions
       0x04,                                // 4 parameters
-      0x02, 0x32,                          // max_request_id = 50
       0x01, 0x04, 0x70, 0x61, 0x74, 0x68,  // path = "path"
-      0x05, 0x09, 0x61, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x69, 0x74,
+      0x01, 0x32,                          // max_request_id = 50
+      0x03, 0x09, 0x61, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x69, 0x74,
       0x79,  // authority = "authority"
       // moqt_implementation:
-      0x07, 0x1c, 0x4d, 0x6f, 0x71, 0x20, 0x54, 0x65, 0x73, 0x74, 0x20, 0x49,
+      0x02, 0x1c, 0x4d, 0x6f, 0x71, 0x20, 0x54, 0x65, 0x73, 0x74, 0x20, 0x49,
       0x6d, 0x70, 0x6c, 0x65, 0x6d, 0x65, 0x6e, 0x74, 0x61, 0x74, 0x69, 0x6f,
       0x6e, 0x20, 0x54, 0x79, 0x70, 0x65};
   MoqtClientSetup client_setup_ = {
@@ -598,11 +602,10 @@
   uint8_t raw_packet_[37] = {0x21, 0x00,
                              0x22,  // type
                              0x01,
-                             0x02,  // version, two parameters
-                             0x02,
-                             0x32,  // max_subscribe_id = 50
+                             0x02,        // version, two parameters
+                             0x02, 0x32,  // max_subscribe_id = 50
                              // moqt_implementation:
-                             0x07, 0x1c, 0x4d, 0x6f, 0x71, 0x20, 0x54, 0x65,
+                             0x05, 0x1c, 0x4d, 0x6f, 0x71, 0x20, 0x54, 0x65,
                              0x73, 0x74, 0x20, 0x49, 0x6d, 0x70, 0x6c, 0x65,
                              0x6d, 0x65, 0x6e, 0x74, 0x61, 0x74, 0x69, 0x6f,
                              0x6e, 0x20, 0x54, 0x79, 0x70, 0x65};
@@ -708,7 +711,7 @@
       0x02,
       0x67,
       0x10,  // delivery_timeout = 10000 ms
-      0x03,
+      0x01,
       0x05,
       0x03,
       0x00,
@@ -788,7 +791,7 @@
       0x0c, 0x14,                          // largest_location = (12, 20)
       0x02,                                // 2 parameters
       0x02, 0x67, 0x10,                    // delivery_timeout = 10000
-      0x04, 0x67, 0x10,                    // max_cache_duration = 10000
+      0x02, 0x67, 0x10,                    // max_cache_duration = 10000
   };
 };